Spotlight Poster
Barely Random Algorithms and Collective Metrical Task Systems
Romain Cosson · Laurent Massoulié
West Ballroom A-D #5807
Abstract:
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 random bits, and achieves the same competitive ratio up to a factor . 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 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 -competitive as soon as . In comparison, a single agent is always -competitive.
Chat is not available.