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.
- N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons, New York, 2000.Google ScholarCross Ref
- Y. Azar and L. Epstein. On-line machine covering. Journal of Scheduling, 1(2):67--77, 1998.Google ScholarCross Ref
- I. Bezakova and V. Dani. Allocating indivisible goods. SIGecom Exchanges, 5.3, 2005. Google ScholarDigital Library
- J. Csirik, H. Kellerer, and G. Woeginger. The exact lpt-bound for maximizing the minimum completion time. Operations Research Letters, 11(5):281--287, 19982. Google ScholarDigital Library
- B. Deuermeyer, D. Friesen, and M. Langston. Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J. Algebraic Discrete Methods, 3(2):190--196, 1982.Google ScholarDigital Library
- D. Golovin. Max-min fair allocation of indivisible goods. Technical Report, Carnegie Mellon University, CMU-CS-05-144, 2005.Google Scholar
- N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Procedeeings of Foundations of Computer Science (FOCS), pages 312--320, 1982.Google ScholarDigital Library
- T. Leighton, C. Lu, S. Rao, and A. Srinivasan. New algorithmic aspects of the local lemma with applications to routing and partitioning. SIAM J. Comput., 31(2):626--641, 2001. Google ScholarDigital Library
- J. K. Lenstra, D. B. Shmoys, and E. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, Series A, 46(2):259--271, 1990. Google ScholarDigital Library
- R. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. ACM Conference on Electronic Commerce, 2004. Google ScholarDigital Library
- D. B. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, Series A, 62:461--474, 1993. Google ScholarDigital Library
- Z. Tan, Y. He, and L. Epstein. Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data. Information and Computation, 1196(1):57--70, 2005. Google ScholarDigital Library
- G. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett., 20(4):149--154, 1997. Google ScholarDigital Library
Index Terms
The Santa Claus problem
Recommendations
Santa Claus schedules jobs on unrelated machines
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computingOne of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time pij if processed on machine i. More ...
Santa Claus Schedules Jobs on Unrelated Machines
† Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011)One of the classic results in scheduling theory is the $2$-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job $j$ requires time $p_{ij}$ if processed on machine $i$. ...
Randomized Approximation for the Set Multicover Problem in Hypergraphs
Let $$b\in {\mathbb {N}}_{\ge 1}$$b N 1 and let $${\mathcal {H}}=(V,{\mathcal {E}})$$H=(V,E) be a hypergraph with maximum vertex degree $${\varDelta }$$Δ and maximum edge size $$l$$l. A set $$b$$b-multicover in $${\mathcal {H}}$$H is a set of edges $$C \...
Comments