The Santa Claus problem

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 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 ∈ Si} 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.

REFERENCES

• 1: N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons, New York, 2000.
• 2: Y. Azar and L. Epstein. On-line machine covering. Journal of Scheduling, 1(2):67--77, 1998.
• 3: Ivona Bezáková , Varsha Dani, Allocating indivisible goods, ACM SIGecom Exchanges, v.5 n.3, p.11-18, April 2005 [doi>10.1145/1120680.1120683]
• 4: 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.
• 5: 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.
• 6: D. Golovin. Max-min fair allocation of indivisible goods. Technical Report, Carnegie Mellon University, CMU-CS-05-144, 2005.
• 7: 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.
• 8: Tom Leighton , Chi-Jen Lu , Satish Rao , Aravind Srinivasan, New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning, SIAM Journal on Computing, v.31 n.2, p.626-641, 2001 [doi>10.1137/S0097539700379760]
• 9: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 10: R. J. Lipton , E. Markakis , E. Mossel , A. Saberi, On approximately fair allocations of indivisible goods, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988792]
• 11: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 12: Zhiyi Tan , Yong He , Leah Epstein, Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data, Information and Computation, v.196 n.1, p.57-70, January 10, 2005 [doi>10.1016/j.ic.2004.10.002]
• 13: G. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett., 20(4):149--154, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, maximin, resource allocation, scheduling, unrelated machines