Concept

Competitive analysis (online algorithm)

Related publications (33)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

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 mu messages to several receivers over separate erasure channels. The sender can broadcast a single message or ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

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

From spheres to spheropolyhedra: generalized Distinct Element Methodology and algorithm analysis

Thomas Liebling, Lionel Pournin

The Distinct Element Method (DEM) is a popular tool to perform granular media simulations. The two key elements this requires are an adequate model for inter-particulate contact forces and an efficient contact detection method. Originally, this method was ...

Springer2009

Real-time 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 m messages to several receivers. The sender can broadcast a single message or a combination (encoding) of mess ...

2008

Online Broadcasting with Network Coding

Christina Fragouli, Lorenzo Keller

Consider a source broadcasting M packets to N receivers over independent erasure channels, where perfect feedback is available from the receivers to the source, and the source is allowed to use coding. We investigate offline and online algorithms that opti ...

2008

Worst-Case Bounds for Gaussian Process Models

Matthias Seeger

We present a competitive analysis of some non-parametric Bayesian algorithms in a worst-case online learning setting, where no probabilistic assumptions about the generation of the data are made. We consider models which use a Gaussian process prior (over ...

2006

An online throughput-competitive algorithm for multicast routing and admission control

Monika Henzinger, Ashish Goel

We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of reque ...

2005

Scheduling multicasts on unit-capacity trees and meshes

Monika Henzinger

This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput model. The problem is a generalization of the edge-disjoint paths problem and is NP-hard both on trees and meshes. We study b ...

2003

Adaptive Brain Interfaces for Communication and Control

José del Rocio Millán Ruiz

This paper describes our work on a portable non-invasive brain-computer interface (BCI), called Adaptive Brain Interfaces (ABI), that analysis online the users spontaneous electroencephalogram (EEG) signals from which a neural classifier recognizes 3 diffe ...

2003