skip to main content
10.1145/1132516.1132522acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

The Santa Claus problem

Published:21 May 2006Publication History

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.

References

  1. N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons, New York, 2000.Google ScholarGoogle ScholarCross RefCross Ref
  2. Y. Azar and L. Epstein. On-line machine covering. Journal of Scheduling, 1(2):67--77, 1998.Google ScholarGoogle ScholarCross RefCross Ref
  3. I. Bezakova and V. Dani. Allocating indivisible goods. SIGecom Exchanges, 5.3, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. D. Golovin. Max-min fair allocation of indivisible goods. Technical Report, Carnegie Mellon University, CMU-CS-05-144, 2005.Google ScholarGoogle Scholar
  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.Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. R. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. ACM Conference on Electronic Commerce, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. D. B. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, Series A, 62:461--474, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. G. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett., 20(4):149--154, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. The Santa Claus problem

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in
          • Published in

            cover image ACM Conferences
            STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
            May 2006
            786 pages
            ISBN:1595931341
            DOI:10.1145/1132516

            Copyright © 2006 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 21 May 2006

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • Article

            Acceptance Rates

            Overall Acceptance Rate1,469of4,586submissions,32%

            Upcoming Conference

            STOC '24
            56th Annual ACM Symposium on Theory of Computing (STOC 2024)
            June 24 - 28, 2024
            Vancouver , BC , Canada

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader