Showing 2024Show all
3 papers · 1 filter
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…
cs.MA2024
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…