2026-07-26T17:19:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10614 2024-03-06T10:46:17Z ddc:004 open_access

Restricted Max-Min Allocation: Approximation and Integrality Gap Cheng, Siu-Wing Mao, Yuchen fair allocation configuration LP approximation integrality gap 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siu-Wing Cheng and Yuchen Mao 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.38 urn:nbn:de:0030-drops-106143 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.38 eng https://creativecommons.org/licenses/by/3.0/legalcode