Distributed Santa Claus via Global Rounding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909004853149696 |
|---|---|
| author | de Vos, Tijn Wennmann, Leo Baumecker, Malte Maus, Yannic Schager, Florian |
| author_facet | de Vos, Tijn Wennmann, Leo Baumecker, Malte Maus, Yannic Schager, Florian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27983 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distributed Santa Claus via Global Rounding de Vos, Tijn Wennmann, Leo Baumecker, Malte Maus, Yannic Schager, Florian Data Structures and Algorithms Distributed, Parallel, and Cluster Computing 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. |
| title | Distributed Santa Claus via Global Rounding |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2604.27983 |