Barely Random Algorithms and Collective Metrical Task Systems

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 2\log n 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(\log 2 n) -competitive as soon as k\geq n 2 .