The Santa Claus problem

We consider the following problem: The Santa Claus has n presents that he wants to distribute among m kids. Each kid has an arbitrary value for each present. Let pij be the value that kid i has for present j. The Santa's goal is to distribute presents in such a way that the least lucky kid is as happy as possible, i.e he tries to maximize mini=1,...,m ∑j∈Si pij where Si is a set of presents received by the i-th kid. Our main result is an O (log log m / log log log m) approximation algorithm for the restricted assignment case of the problem when pij ∈ {pj, 0} (i.e. when present j has either value Pj or 0 for each kid). Our algorithm is based on rounding a certain natural exponentially large linear programming relaxation usually referred to as the configuration LP. We also show that the configuration LP has an integrality gap of Ω(m1/2) in the general case, when p ij can be arbitrary. Copyright 2006 ACM.