The Santa Claus problem
- 21 May 2006
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
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 Ω(m1/2) in the general case, when pij can be arbitrary.Keywords
This publication has 12 references indexed in Scilit:
- Allocating indivisible goodsACM SIGecom Exchanges, 2005
- Optimal on-line algorithms for the uniform machine scheduling problem with ordinal dataInformation and Computation, 2005
- On approximately fair allocations of indivisible goodsPublished by Association for Computing Machinery (ACM) ,2004
- New Algorithmic Aspects of the Local Lemma with Applications to Routing and PartitioningSIAM Journal on Computing, 2001
- On-line machine coveringJournal of Scheduling, 1998
- A polynomial-time approximation scheme for maximizing the minimum machine completion timeOperations Research Letters, 1997
- An approximation algorithm for the generalized assignment problemMathematical Programming, 1993
- The exact LPT-bound for maximizing the minimum completion timeOperations Research Letters, 1992
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor SystemSIAM Journal on Algebraic Discrete Methods, 1982