Publications related to 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

Development of a Data Concentrator ASIC for the High Luminosity upgrade of the CMS Outer Tracker detector with tracking trigger

Simone Scarfì

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 ...

EPFL2021

A Catalyst Framework for Minimax Optimization

Negar Kiyavash

We introduce a generic two-loop scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated dual problem and takes full advantage of existing ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2020

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

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

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

Hyphenated Analytical Techniques for Studying the Speciation and Fate of Contaminants and Nanoparticles in Waste Treatment and Bioenergy Processes

Debora Foppiano

The widespread use of nanoparticles (NPs) and other potentially ecotoxic chemical compounds to enhance the quality of consumer products has raised concern about their fate in the environment. Indeed, those products have to be ultimately disposed of and alo ...

EPFL2019

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

No time for drifting: Comparing performance and applicability of signal detrending algorithms for real-time fMRI

Dimitri Nestor Alice Van De Ville, Frank Scharnowski, Yury Koush, Rotem Roza Kopel

As a consequence of recent technological advances in the field of functional magnetic resonance imaging (fMRI), results can now be made available in real-time. This allows for novel applications such as online quality assurance of the acquisition, intra-op ...

2019

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

IEEE COMPUTER SOC2019

Real-Time Generative Hand Modeling and Tracking

Anastasia Tkach

In our everyday life we interact with the surrounding environment using our hands. A main focus of recent research has been to bring such interaction to virtual objects, such as the ones projected in virtual reality devices, or super-imposed as holograms i ...

EPFL2018

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

Optimal Layered Representation for Adaptive Interactive Multiview Video Streaming

Pascal Frossard, Thomas Maugey, Laura Toni, Nikolaos Thomos, Ana Karina De Abreu Goes

We consider an interactive multiview video streaming (IMVS) system where clients select their preferred viewpoint in a given navigation window. To provide high quality IMVS, many high quality views should be transmitted to the clients. However, this is not ...

Elsevier2015

On multiscale methods in Petrov-Galerkin formulation

Patrick Henning

In this work we investigate the advantages of multiscale methods in Petrov-Galerkin (PG) formulation in a general framework. The framework is based on a localized orthogonal decomposition of a high dimensional solution space into a low dimensional multisca ...

Springer2015

A hyphenated SMPS-ICPMS coupling setup: Size-resolved element specific analysis of airborne nanoparticles

Christian Ludwig, Mohamed Tarik, Adrian Hess

Physical and chemical characterization of gas borne particles in the nanometer to sub micrometer size range includes knowledge about particle size distribution and chemical composition, possibly with a high time resolution. However, most of the available t ...

Elsevier Sci Ltd2015