5 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…
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…
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…