  We consider hypergraphs on vertices $P\cup R$ where each hyperedge contains
exactly one vertex in $P$. Our goal is to select a matching that covers all of
$P$, but we allow each selected hyperedge to drop all but an
$(1/\alpha)$-fraction of its intersection with $R$ (thus relaxing the matching
constraint). Here $\alpha$ is to be minimized. We dub this problem the
Combinatorial Santa Claus problem, since we show in this paper that this
problem and the Santa Claus problem are almost equivalent in terms of their
approximability.
  The non-trivial observation that any uniform regular hypergraph admits a
relaxed matching for $\alpha = O(1)$ was a major step in obtaining a constant
approximation rate for a special case of the Santa Claus problem, which
received great attention in literature. It is natural to ask if the uniformity
condition can be omitted. Our main result is that every (non-uniform) regular
hypergraph admits a relaxed matching for $\alpha = O(\log\log(|R|))$, when all
hyperedges are sufficiently large (a condition that is necessary). In
particular, this implies an $O(\log\log(|R|))$-approximation algorithm for the
Combinatorial Santa Claus problem with large hyperedges.
