Online graph coloring shows gap between random and fixed methods
Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Graph coloring means giving colors to points in a way that connected points get different colors. Doing this without knowing the whole graph at once is called online graph coloring and is tricky. The authors improved mathematical bounds that show randomized methods can use fewer colors on average than any fixed (deterministic) method can. This means using randomness helps solve the problem better when the order of points is unknown in advance.
What this means in practice
- •For network schedulers: Design schedulers that assign resources by modeling conflicts as graph coloring needing fewer colors with randomized approaches.
- •For memory management teams: Improve allocation strategies by understanding the limits on coloring-based conflict resolution with deterministic versus randomized algorithms.
A theory result. No direct application yet.
Authors
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
Abstract
We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(n / \log^2 n)$ for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of $O(n / \log n)$ for randomized algorithms by Halldórsson (1997), and (3) an upper bound of $O(n / \log \log n)$ for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of $Ω(n / \log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\log \log n)^2 / \log^2 n)$ for randomized algorithms. 3. A new upper bound of $O(n / (\log \log n)^{2-\varepsilon})$ for deterministic algorithms for every fixed $\varepsilon>0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n)^2)$. We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.