research-article

Santa claus meets hypergraph matchings

Authors:

Arash Asadpour,

Amin SaberiAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 8, Issue 3

Article No.: 24, Pages 1 - 9

https://doi.org/10.1145/2229163.2229168

Published: 24 July 2012 Publication History

Abstract

We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as the Santa Claus problem. There are m items and n players. Every item has some nonnegative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lovász local lemma that the integrality gap of a certain configuration LP for the problem is no worse than some (unspecified) constant. This gives a polynomial-time algorithm to estimate the optimum value of the problem within a constant factor, but does not provide a polynomial-time algorithm for finding a corresponding allocation.

We use a different approach to analyze the integrality gap. Our approach is based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is no worse than 1/4. Our proof provides a local search algorithm which finds the corresponding allocation, but is nonconstructive in the sense that this algorithm is not known to converge to a local optimum in a polynomial number of steps.

References

[1]

Aharoni, R. 2000. Hall's theorem for hypergraphs. J. Graph Theory 35, 83--88.

Digital Library

[2]

Asadpour, A., Feige, U., and Saberi, A. 2008. Santa Claus meets hypergraph matchings. In Proceedings of the APPROX-RANDOM Conference. 10--20.

Digital Library

[3]

Asadpour, A. and Saberi, A. 2010. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput. 39, 7, 2970--2989.

Digital Library

[4]

Bansal, N. and Sviridenko, M. 2006. The santa claus problem. In Proceedings of the Symposium on Theory of Computing (STOC'06). 31--40.

Digital Library

[5]

Bezáková, I. and Dani, V. 2005. Allocating indivisible goods. SIGecom Exchanges 5, 3, 11--18.

Digital Library

[6]

Brams, S. and Taylor, A. D. 1996. Fair Division: From Cake Cutting to Dispute Resolution. Cambridge University Press.

[7]

Dobzinski, S. and Schapira, M. 2006. An improved approximation algorithm for combinatorial auctions with submodular bidders. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06). 1064--1073.

Digital Library

[8]

Ebenlendr, T., Krcal, M., and Sgall, J. 2008. Graph balancing: A special case of scheduling unrelated parallel machines. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'08). 483--490.

Digital Library

[9]

Feige, U. 2008. On allocations that maximize fairness. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'08). 287--293.

Digital Library

[10]

Feige, U. 2009. On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39, 1, 122--142.

Digital Library

[11]

Feige, U. and Vondrák, J. 2006. Approximation algorithms for allocation problems: Improving the factor of 1-1/e. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'06). 667--676.

Digital Library

[12]

Haeupler, B., Saha, B., and Srinivasan, A. 2010. New constructive aspects of the lovasz local lemma. http://arxiv.org/abs/1001.1231

[13]

Haxell, P. E. 1995. A condition for matchability in hypergraphs. Graphs Combin. 11, 245--248.

Digital Library

[14]

Johnson, D. S., Papadimitriou, C. H., and Yannakakis, M. 1988. How easy is local search&quest; J. Comput. Syst. Sci. 37, 1, 79--100.

Digital Library

[15]

Kessler, O. 1989. Matchings in hypergraphs. M.S. thesis, Technion.

[16]

Kuhn, H. W. 1955. The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2, 83--97.

[17]

Lenstra, J. K., Shmoys, D. B., and Tardos, E. 1990. Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259--271.

Digital Library

[18]

Steinhaus, H. 1948. The problem of fair division. Econometrica 16, 101--148.

[19]

Vondrak, J. 2008. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the Symposium on Theory of Computing (STOC'08). 67--74.

Digital Library

Cited By

Brown ALaddha ASingh M(2024)Fast Algorithms for Maximizing the Minimum Eigenvalue in Fixed DimensionOperations Research Letters10.1016/j.orl.2024.107186(107186)Online publication date: Sep-2024
https://doi.org/10.1016/j.orl.2024.107186
Ko SChen HCheng SHon WLiao C(2024)Polynomial-time Combinatorial Algorithm for General Max–Min Fair AllocationAlgorithmica10.1007/s00453-023-01105-386:2(485-504)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00453-023-01105-3
Bamas ÉRohwedder LSaha BServedio R(2023)Better Trees for Santa ClausProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585174(1862-1875)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585174
Show More Cited By

Index Terms

Santa claus meets hypergraph matchings
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Hypergraphs
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Better Trees for Santa Claus
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC’09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former ...
Santa Claus Meets Hypergraph Matchings
APPROX '08 / RANDOM '08: Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques

We consider the problem of max-min fair allocation of indivisible goods. Our focus will be on the restricted version of the problem in which there are <em>m</em>items, each of which associated with a non-negative value. There are also <em>n</em>players ...
Hardness of Approximate Hypergraph Coloring

We introduce the notion of covering complexity of a verifier for probabilistically checkable proofs (PCPs). Such a verifier is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The verifier is also given a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 8, Issue 3

July 2012

257 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2229163

Issue’s Table of Contents

Copyright © 2012 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: 24 July 2012

Accepted: 01 December 2009

Received: 01 July 2009

Published in TALG Volume 8, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
595
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brown ALaddha ASingh M(2024)Fast Algorithms for Maximizing the Minimum Eigenvalue in Fixed DimensionOperations Research Letters10.1016/j.orl.2024.107186(107186)Online publication date: Sep-2024
https://doi.org/10.1016/j.orl.2024.107186
Ko SChen HCheng SHon WLiao C(2024)Polynomial-time Combinatorial Algorithm for General Max–Min Fair AllocationAlgorithmica10.1007/s00453-023-01105-386:2(485-504)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00453-023-01105-3
Bamas ÉRohwedder LSaha BServedio R(2023)Better Trees for Santa ClausProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585174(1862-1875)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585174
Botan SRitossa ASuzuki MWalsh T(2023)Maximin Fair Allocation of Indivisible Items Under Cost UtilitiesAlgorithmic Game Theory10.1007/978-3-031-43254-5_13(221-238)Online publication date: 4-Sep-2023
https://doi.org/10.1007/978-3-031-43254-5_13
Onn S(2022)Matching orderable and separable hypergraphsOptimization Letters10.1007/s11590-022-01854-016:5(1393-1401)Online publication date: 2-Feb-2022
https://doi.org/10.1007/s11590-022-01854-0
Aronshtam LIlani HShufan E(2022)Perfect matching in bipartite hypergraphs subject to a demand graphAnnals of Operations Research10.1007/s10479-022-05073-9321:1-2(39-48)Online publication date: 28-Nov-2022
https://doi.org/10.1007/s10479-022-05073-9
Cheng SMao Y(2022)Restricted Max-Min Allocation: Integrality Gap and Approximation AlgorithmAlgorithmica10.1007/s00453-022-00942-y84:7(1835-1874)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00453-022-00942-y
Ko SChen HCheng SHon WLiao C(2021)General Max-Min Fair AllocationComputing and Combinatorics10.1007/978-3-030-89543-3_6(63-75)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_6
Jansen KRohwedder L(2020)A Quasi-Polynomial Approximation for the Restricted Assignment ProblemSIAM Journal on Computing10.1137/19M128257X49:6(1083-1108)Online publication date: 3-Nov-2020
https://doi.org/10.1137/19M128257X
Graf AHaxell P(2020)Finding independent transversals efficientlyCombinatorics, Probability and Computing10.1017/S0963548320000127(1-27)Online publication date: 14-May-2020
https://doi.org/10.1017/S0963548320000127
Show More Cited By

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents