Concept
Competitive analysis (online algorithm)
Related publications (33)
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 competitive ...
EPFL2023Follow the Clairvoyant: an Imitation Learning Approach to Optimal Control
Giancarlo Ferrari Trecate, John Lygeros, Luca Furieri, Florian Dörfler, Andrea Martin
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 ...
Elsevier2023Sonomyographic Prosthetic Interacion: Online Simultaneous and Proportional Control of Wrist and Hand Motions Using Semisupervised Learning
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 INC2022Learning-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 ...
2021How 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 algori ...
EPFL2021Real-Time Musculoskeletal Kinematics and Dynamics Analysis Using Marker- and IMU-Based Solutions in Rehabilitation
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 ...
2021Development of a Data Concentrator ASIC for the High Luminosity upgrade of the CMS Outer Tracker detector with tracking trigger
With the increasing capabilities of the microelectronics technology, future particle detectors in high energy physics will be able to yield high-level features that are not only simple geometrical positions or energy measurement in the silicon sensors used ...
EPFL2021Dynamic Balanced Graph Partitioning
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 ...
2020Nested Convex Bodies are Chaseable
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 ...
SPRINGER2019The (h, k)-Server Problem on Bounded Depth Trees
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