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 p ij 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 min i=1,...,m sum j ∈ S i p ij where S i 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 p ij ∈ p j ,0 (i.e. when present j has either value p j 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 Ω(m 1/2 ) in the general case, when p ij can be arbitrary.

Authors

• Nikhil Bansal 0001
• Maxim Sviridenko

Keywords

• approximation algorithms
• maximin
• resource allocation
• scheduling
• unrelated machines