  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
$(4+\varepsilon)$-approximation for Santa Claus. This factor also compares
against a natural, compact LP for Santa Claus.
