A Tale of Santa Claus, Hypergraphs and Matroids
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2018
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909980260564992 |
|---|---|
| author | Davies, Sami Rothvoss, Thomas Zhang, Yihao |
| author_facet | Davies, Sami Rothvoss, Thomas Zhang, Yihao |
| contents | A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child $i$ has for a present $j$ is of the form $p_{ij} \in \{ 0,p_j\}$. A polynomial time algorithm by Annamalai et al. gives a $12.33$-approximation and is based on a modification of Haxell's hypergraph matching argument.
In this paper, we introduce a matroid version of the Santa Claus problem. Our algorithm is also based on Haxell's augmenting tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a $(6+\varepsilon)$-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1807_07189 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | A Tale of Santa Claus, Hypergraphs and Matroids Davies, Sami Rothvoss, Thomas Zhang, Yihao Data Structures and Algorithms Discrete Mathematics A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child $i$ has for a present $j$ is of the form $p_{ij} \in \{ 0,p_j\}$. A polynomial time algorithm by Annamalai et al. gives a $12.33$-approximation and is based on a modification of Haxell's hypergraph matching argument. In this paper, we introduce a matroid version of the Santa Claus problem. Our algorithm is also based on Haxell's augmenting tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a $(6+\varepsilon)$-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus. |
| title | A Tale of Santa Claus, Hypergraphs and Matroids |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/1807.07189 |