Search papers, labs, and topics across Lattice.
This paper investigates the Santa Claus problem, an NP-hard resource allocation problem, within the CONGEST distributed computing model. They present the first distributed algorithms for this problem, achieving an $\mathcal{O}(\log n/\log \log n)$-approximation in $\hat \Theta(\sqrt n+D)$ rounds. A matching $\widetilde\Omega(\sqrt n+D)$-round lower bound is also proven, establishing fundamental limits on the approximability of the problem in distributed settings.
Even approximately fair gift-giving is surprisingly hard in distributed systems: achieving any approximation for the Santa Claus problem requires $\Omega(\sqrt{n} + D)$ rounds.
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 \Theta(\sqrt n+D)$ rounds, where our $\widetilde\Omega(\sqrt n+D)$-round lower bound is even stronger and holds for any approximation.
