4 papers · 1 filter
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 $n…