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 algorithm and is based on a modification of Haxell’s hypergraph matching argument. This factor compares to the value of an exponential size configuration LP.

 

We introduce a matroid version of the Santa Claus problem with unit size presents and design an algorithm which gives a polynomial time \$(3 + \varepsilon)\$-approximation compared to a natural, compact LP. Our algorithm is also based on Haxell’s augmentation tree, but despite the greater generality, it is cleaner than previous methods. Our result can then be used as a blackbox to obtain a \$(6 + \varepsilon)\$-approximation for Santa Claus (with arbitrary present sizes). This factor also compares against a natural, compact LP for Santa Claus.