Abstract
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 sumj ¿ 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 O(m1/2) in the general case, when pij can be arbitrary.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06, Seattle WA, USA, May 21-23, 2006) |
| Place of Publication | New York |
| Publisher | Association for Computing Machinery, Inc |
| Pages | 31-40 |
| ISBN (Print) | 1-59593-134-1 |
| Publication status | Published - 2006 |