Distributed Santa Claus via Global Rounding
This work provides the first distributed results for a classic NP-hard allocation problem, establishing tight complexity bounds for approximation in the CONGEST model.
The paper presents the first distributed algorithm for the Santa Claus problem in the CONGEST model, achieving an O(log n / log log n)-approximation in Õ(√n + D) rounds, with a matching lower bound for any approximation.
In this paper, we consider the Santa Claus problem in the CONGEST model. This NP-hard problem can be modeled as a bipartite graph of children and gifts where an edge indicates that a child desires a gift. Notably, each gift can have a different value. The goal is to assign the gifts to the children such that the least happy child is as happy as possible. Even though this is a well-studied problem in the sequential setting, we obtain the first results the distributed setting. In particular, we show that the complexity of computing an $\mathcal{O}(\log n/\log \log n)$-approximation is $\hat Θ(\sqrt n+D)$ rounds, where our $\widetildeΩ(\sqrt n+D)$-round lower bound is even stronger and holds for any approximation.