Publications associées à Competitive analysis (online algorithm)

Beyond worst-case analysis, with or without predictions

In this thesis we design online combinatorial optimization algorithms for beyond worst-case analysis settings. In the first part, we discuss the online matching problem and prove that, in the edge arrival model, no online algorithm can achieve a competiti ...

EPFL2023

Follow the Clairvoyant: an Imitation Learning Approach to Optimal Control

Giancarlo Ferrari Trecate, Luca Furieri, John Lygeros, Andrea Martin, Florian Dörfler

We consider control of dynamical systems through the lens of competitive analysis. Most prior work in this area focuses on minimizing regret, that is, the loss relative to an ideal clairvoyant policy that has noncausal access to past, present, and future d ...

Elsevier2023

Sonomyographic Prosthetic Interacion: Online Simultaneous and Proportional Control of Wrist and Hand Motions Using Semisupervised Learning

Xingchen Yang

Human hands play a very important role in daily object manipulation. Current prosthetic hands are capable of mimicking most functions of the human hand, but how to interact with prosthetic hands based on human intentions remains an open problem. In this ar ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds

Adam Teodor Polak, Marek Elias

We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We d ...

2021

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

EPFL2021

Real-Time Musculoskeletal Kinematics and Dynamics Analysis Using Marker- and IMU-Based Solutions in Rehabilitation

Dimitar Yuriev Stanev

This study aims to explore the possibility of estimating a multitude of kinematic and dynamic quantities using subject-specific musculoskeletal models in real-time. The framework was designed to operate with marker-based and inertial measurement units enab ...

2021

Dynamic Balanced Graph Partitioning

Georg Stefan Schmid, Andreas Loukas

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to servi ...

SIAM Publications2020

Nested Convex Bodies are Chaseable

Marek Elias

In the Convex Body Chasing problem, we are given an initial point v0. Rd and an online sequence of n convex bodies F1,..., Fn. When we receive Ft, we are required to move inside Ft. Our goal is to minimize the total distance traveled. This fundamental onli ...

SPRINGER2020

The (h, k)-Server Problem on Bounded Depth Trees

Marek Elias

We study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h

ASSOC COMPUTING MACHINERY2019

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Hakan Gökcesu, Kaan Gökcesu

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit ...

2019

Detecting EEG correlates during preparation of complex driving maneuvers

Lucian Andrei Gheorghe

The main focus of this research is the development of real-time recording and analysis devices and algorithms for detecting Electroencephalography (EEG) correlates of steering actions. First, offline analysis where performed in a high fidelity driving simu ...

EPFL2017

The weighted averages algorithm revisited

Juan Ramon Mosig

The classic weighted averages (WA) algorithm for the evaluation of Sommerfeld-like integrals is reviewed and reappraised. As a result, a new version of the WA algorithm, called generalized WA, is introduced. The new version can be considered as a generaliz ...

Institute of Electrical and Electronics Engineers2012

Infinite integrals with the weighted averages algorithm

Juan Ramon Mosig, Athanasios Polymeridis

A new version of the weighted averages (WA) algorithm, called generalized WA, is introduced. Generalized WA exhibit a more compact formulation, devoid of iterative and recursive steps, and a wider range of applications. It is more robust, as it provides a ...

2011

Exponential Natural Evolution Strategies

Daniël Pieter Wierstra, Tom Schaul

The family of natural evolution strategies (NES) offers a principled approach to real-valued evolutionary optimization by following the natural gradient of the expected fitness. Like the well-known CMA-ES, the most competitive algorithm in the field, NES c ...

2010

Delay with network coding and feedback

Christina Fragouli, Lorenzo Keller

We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of μ messages to several receivers over separate erasure channels. The sender can broad- cast a single message or ...

2009