7 papers
Online Scheduling with a Stochastic Signal
Romain Cosson, Jingwei Li, Alexander Lindermayr +1
Nonclairvoyant scheduling is a fundamental online model in which processing times are initially unknown to the scheduler. Unfortunately, for important objectives such as total comp…
Randomized -server in polynomial time
Christian Coester, Romain Cosson
We study the design of computationally efficient randomized algorithms for the -server problem. Existing randomized algorithms with the best known competitive ratios are, on the…
Contextual Online Bilateral Trade
Romain Cosson, Federico Fusco, Anupam Gupta +3
We study repeated bilateral trade when the valuations of the sellers and the buyers are contextual. More precisely, the agents' valuations are given by the inner product of a conte…
The value of random zero-sum games
Romain Cosson, Laurent Massoulié
We study the value of a two-player zero-sum game on a random matrix , defined by . In the setting where…
Non-Clairvoyant Scheduling with Progress Bars
Ziyad Benomar, Romain Cosson, Alexander Lindermayr +1
In non-clairvoyant scheduling, the goal is to minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization…
Barely Random Algorithms and Collective Metrical Task Systems
Romain Cosson, Laurent Massoulié
We consider metrical task systems on general metric spaces with points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only $2…