Santa claus meets hypergraph matchings

We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as the Santa Claus problem. There are m items and n players. Every item has some non-negative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lov asz local lemma that the integrality gap of a certain conguration LP for the problem is no worse than some (unspecied) constant. This gives a polynomial time algorithm to estimate the optimum value of the problem within a constant factor, but does not provide a polynomial time algorithm for nding a corresponding allocation. In this paper, we use a dierent approach to analyze the integrality gap. Our approach is based upon local search techniques for nding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the conguration LP is no worse than 1 4 . Our proof provides a local search algorithm which nds the corresponding allocation, but is nonconstructive in the sense that this algorithm is not known to converge to a local optimum in a polynomial number of steps.