8 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 $n…
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…
Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
Xingjian Bai, Christian Coester, Romain Cosson
Introduced by Papadimitriou and Yannakakis in 1989, layered graph traversal is a central problem in online algorithms and mobile computing that has been studied for several decades…
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…
Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph
Romain Cosson
We investigate two fundamental problems in mobile computing: exploration and rendezvous, with two distinct mobile agents in an unknown graph. The agents may communicate by reading…