Showing 2024 · cs.DSShow all
2 papers · 2 filters
cs.DS2024
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…
cs.DS2024
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…