Document Open Access Logo

Restricted Max-Min Allocation: Approximation and Integrality Gap

Authors Siu-Wing Cheng , Yuchen Mao

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.38.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • fair allocation
  • configuration LP
  • approximation
  • integrality gap

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most 4. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a (6 + delta)-approximation algorithm where delta can be any positive constant, and there is still a gap of roughly 2. In this paper, we narrow the gap significantly by proposing a (4+delta)-approximation algorithm where delta can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is poly(m,n)* n^{poly(1/(delta))} where n is the number of players and m is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to 3 + 21/26 =~ 3.808.

Cite As Get BibTex

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Allocation: Approximation and Integrality Gap. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.38

Author Details

Siu-Wing Cheng
  • Department of Computer Science and Engineering, HKUST, Hong Kong
Yuchen Mao
  • Department of Computer Science and Engineering, HKUST, Hong Kong

References

  1. C. Annamalai, C. Kalaitzis, and O. Svensson. Combinatorial Algorithm for Restricted Max-Min Fair Allocation. ACM Transactions on Algorithms, 13(3):37:1-37:28, 2017. Google Scholar
  2. A. Asadpour, U. Feige, and A. Saberi. Santa Claus meets hypergraph matchings. ACM Transactions on Algorithms, 8(3):24:1-24:9, 2012. Google Scholar
  3. A. Asadpour and A. Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. In Proceedings of the 39th ACM Symposium on Theory of Computing, pages 114-121, 2007. Google Scholar
  4. N. Bansal and M. Sviridenko. The Santa Claus problem. In Proceedings of the 38th ACM Symposium on Theory of Computing, pages 31-40, 2006. Google Scholar
  5. M. Bateni, M. Charikar, and V. Guruswami. Max-Min Allocation via Degree Lower-bounded Arborescences. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 543-552, 2009. Google Scholar
  6. I. Bezáková and Varsha Dani. Allocating indivisible goods. SIGecom Exchanges, 5(3):11-18, 2005. Google Scholar
  7. D. Chakrabarty, J. Chuzhoy, and S. Khanna. On Allocating Goods to Maximize Fairness. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, pages 107-116, 2009. Google Scholar
  8. S.-W. Cheng and Y. Mao. Integrality Gap of the Configuration LP for the Restricted Max-Min Fair Allocation. CoRR, abs/1807.04152, 2018. URL: http://arxiv.org/abs/1807.04152.
  9. S.-W. Cheng and Y. Mao. Restricted Max-Min Fair Allocation. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, pages 37:1-37:13, 2018. Google Scholar
  10. S. Davies, T. Rothvoss, and Y. Zhang. A Tale of Santa Claus, Hypergraphs and Matroids. CoRR, abs/1807.07189, 2018. URL: http://arxiv.org/abs/1807.07189.
  11. U. Feige. On allocations that maximize fairness. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, pages 287-293, 2008. Google Scholar
  12. B. Haeupler, B. Saha, and A. Srinivasan. New Constructive Aspects of the Lovász Local Lemma. Journal of the ACM, 58(6):28:1-28:28, 2011. Google Scholar
  13. P.E. Haxell. A condition for matchability in hypergraphs. Graphs and Combinatorics, 11(3):245-248, 1995. Google Scholar
  14. J.E. Hopcroft and R.M. Karp. An n^5/2 algorithm for maximum matching in bipartitie graphs. SIAM Journal on Computing, 2:225-231, 1973. Google Scholar
  15. K. Jansen and L. Rohwedder. A note on the integrality gap of the configuration LP for restricted Santa Claus. CoRR, abs/1807.03626, 2018. URL: http://arxiv.org/abs/1807.03626.
  16. J.K. Lenstra, D.B. Shmoys, and É. Tardos. Approximation Algorithms for Scheduling Unrelated Parallel Machines. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 217-224, 1987. Google Scholar
  17. L. Polacek and O. Svensson. Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation. In 39th International Colloquium on Automata, Languages, and Programming, pages 726-737, 2012. Google Scholar
  18. B. Saha and A. Srinivasan. A New Approximation Technique for Resource-Allocation Problems. In Proceedings of the 1st Symposium on Innovations in Computer Science, pages 342-357, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact