Distributed Santa Claus via Global Rounding

Abstract

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{\hat{I}}˜(\sqrt{n}+D)$ rounds, where our $\tilde{\hat{I}}\text{c◯}(\sqrt{n}+D)$-round lower bound is even stronger and holds for any approximation.

abstract shortened for arXiv requirements