Skip to yearly menu bar Skip to main content


Spotlight Poster

Barely Random Algorithms and Collective Metrical Task Systems

Romain Cosson · Laurent Massoulié

West Ballroom A-D #5807
[ ]
[ Paper [ Slides [ Poster [ OpenReview
Thu 12 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: We consider metrical task systems on general metric spaces with n points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only 2logn random bits, and achieves the same competitive ratio up to a factor 2. This provides the first order-optimal barely random algorithms for metrical task systems, i.e. which use a number of random bits that does not depend on the number of requests addressed to the system. We discuss implications on various aspects of online decision making such as: distributed systems, advice complexity and transaction costs, suggesting broad applicability. We put forward an equivalent view that we call collective metrical task systems where k agents in a metrical task system team up, and suffer the average cost paid by each agent. Our results imply that such team can be O(log2n)-competitive as soon as kn2. In comparison, a single agent is always Ω(n)-competitive.

Chat is not available.