DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2019.38

Restricted Max-Min Allocation: Approximation and Integrality Gap

Authors: Siu-Wing Cheng and Yuchen Mao

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

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

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)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2019.38,
  author =	{Cheng, Siu-Wing and Mao, Yuchen},
  title =	{{Restricted Max-Min Allocation: Approximation and Integrality Gap}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.38},
  URN =		{urn:nbn:de:0030-drops-106143},
  doi =		{10.4230/LIPIcs.ICALP.2019.38},
  annote =	{Keywords: fair allocation, configuration LP, approximation, integrality gap}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.37

Restricted Max-Min Fair Allocation

Authors: Siu-Wing Cheng and Yuchen Mao

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: 4+delta for estimation and 6 + 2 sqrt{10} + delta ~~ 12.325 + delta for construction, where delta is an arbitrarily small constant greater than 0. We propose an algorithm that constructs an allocation with value within a factor 6 + delta from the optimum for any constant delta > 0. The running time is polynomial in the input size for any constant delta chosen.

Cite as

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Fair Allocation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2018.37,
  author =	{Cheng, Siu-Wing and Mao, Yuchen},
  title =	{{Restricted Max-Min Fair Allocation}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.37},
  URN =		{urn:nbn:de:0030-drops-90418},
  doi =		{10.4230/LIPIcs.ICALP.2018.37},
  annote =	{Keywords: Fair allocation, approximation, local search}
}

Search Results

Documents authored by Mao, Yuchen

Restricted Max-Min Allocation: Approximation and Integrality Gap

Abstract

Cite as

Restricted Max-Min Fair Allocation

Abstract

Cite as

Thanks for your feedback!

Could not send message