# Barely Random Algorithms and Collective Metrical Task Systems

arXiv: https://arxiv.org/abs/2403.11267 · HTML: https://mlsanity.com/paper/2403.11267/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2024.

## Built on by (most cited first, 2 of 2)

- [Learning-Augmented Online Bidding in Stochastic Settings](https://mlsanity.com/paper/2510.25582/) (2025)
- [Competitive Algorithms for Multi-Agent Ski-Rental Problems](https://mlsanity.com/paper/2507.15727/) (2025)

## Abstract (arXiv)

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 2log 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 a team can be O(log2 n)-competitive as soon as k≥ n2. In comparison, a single agent is always Omega(n)-competitive.