More Web Proxy on the site http://driver.im/

research-article

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Authors:

Chidambaram Annamalai,

Christos Kalaitzis,

Ola SvenssonAuthors Info & Claims

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

Article No.: 37, Pages 1 - 28

https://doi.org/10.1145/3070694

Published: 26 May 2017 Publication History

Abstract

We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+ ε. In contrast, however, the best-known approximation algorithm for the problem has an unspecified large constant guarantee.

In this article, we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [13] for hypergraph matchings and later used in this context by Asadpour, Feige, and Saberi [2]. For our local search procedure to terminate in polynomial time, we introduce several new ideas, such as lazy updates and greedy players. Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the Configuration-LP only in the analysis.

References

[1]

Chidambaram Annamalai. 2016. Finding perfect matchings in bipartite hypergraphs. To appear in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (2016).

Digital Library

[2]

Arash Asadpour, Uriel Feige, and Amin Saberi. 2012. Santa Claus meets hypergraph matchings. ACM Trans. Algor. (TALG) 8, 3 (2012), 24.

Digital Library

[3]

Arash Asadpour and Amin Saberi. 2007. An approximation algorithm for max-min fair allocation of indivisible goods. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC’07). ACM, New York, 114--121.

Digital Library

[4]

Nikhil Bansal and Maxim Sviridenko. 2006. The Santa Claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, 31--40.

Digital Library

[5]

MohammadHossein Bateni, Moses Charikar, and Venkatesan Guruswami. 2009. MaxMin allocation via degree lower-bounded arborescences. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09). 543--552.

Digital Library

[6]

Ivona Bezáková and Varsha Dani. 2005. Allocating indivisible goods. ACM SIGecom Exch. 5, 3 (2005), 11--18.

Digital Library

[7]

Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. 2009. On allocating goods to maximize fairness. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS’09). 107--116.

Digital Library

[8]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd ed. MIT Press. Retrieved from http://mitpress.mit.edu/books/introduction-algorithms.

Digital Library

[9]

Uriel Feige. 2008a. On allocations that maximize fairness. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 287--293.

Digital Library

[10]

Uriel Feige. 2008b. On estimation algorithms versus approximation algorithms. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 2. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

[11]

Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. 2011. New constructive aspects of the lovasz local lemma. J. ACM (JACM) 58, 6 (2011), 28.

Digital Library

[12]

G. H. Hardy and S. Ramanujan. 1918. Asymptotic formulae in combinatory analysis. Proceedings of the London Mathematical Society s2-17, 1 (1918), 75--115.

[13]

Penny E. Haxell. 1995. A condition for matchability in hypergraphs. Graphs Combinator. 11, 3 (1995), 245--248.

Digital Library

[14]

Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 1--3 (1990), 259--271.

Digital Library

[15]

Lukas Polacek and Ola Svensson. 2012. Quasi-polynomial local search for restricted max-min fair allocation. In Automata, Languages, and Programming. Springer, 726--737.

Digital Library

[16]

Barna Saha and Aravind Srinivasan. 2010. A new approximation technique for resource-allocation problems. In Proceedings of the International Conference on Supercomputing (ICS’10). 342--357.

[17]

Alexander Schrijver. 2002. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science 8 Business Media.

[18]

Ola Svensson. 2012. Santa Claus schedules jobs on unrelated machines. SIAM J. Comput. 41, 5 (2012), 1318--1341.

Cited By

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
Nguyen TRothe J(2023)Fair and efficient allocation with few agent types, few item types, or small value levelsArtificial Intelligence10.1016/j.artint.2022.103820314(103820)Online publication date: Jan-2023
https://doi.org/10.1016/j.artint.2022.103820
Show More Cited By

Index Terms

Combinatorial Algorithm for Restricted Max-Min Fair Allocation
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Combinatorial algorithm for restricted max-min fair allocation
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms

We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a ...
On (1, $$\epsilon $$∈)-Restricted Max---Min Fair Allocation Problem

We study the max---min fair allocation problem in which a set of m indivisible items are to be distributed among n agents such that the minimum utility among all agents is maximized. In the restricted setting, the utility of each item j on agent i is ...
Restricted Max-Min Allocation: Integrality Gap and Approximation Algorithm
Abstract
Given a set of players P, a set of indivisible resources R, and a set of non-negative values ${v_{pr}}_{p \in P, r \in R}$ , an allocation is a partition of R into disjoint subsets ${C_{p}}_{p \in P}$ so that each player p is assigned the resources in $C_{p}$ . The max-min fair ... $_{}_{_{}}_{}$ $_{}$ $_{}_{}$ $_{}$ $\frac{}{}$

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 13, Issue 3

July 2017

390 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3058789

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2017 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: 26 May 2017

Accepted: 01 March 2017

Revised: 01 November 2016

Received: 01 September 2015

Published in TALG Volume 13, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

School of Basic Sciences, EPFL
ERC Starting

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
448
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Nguyen TRothe J(2023)Fair and efficient allocation with few agent types, few item types, or small value levelsArtificial Intelligence10.1016/j.artint.2022.103820314(103820)Online publication date: Jan-2023
https://doi.org/10.1016/j.artint.2022.103820
Cheng S(2022)Multistage online maxmin allocation of indivisible entitiesTheoretical Computer Science10.1016/j.tcs.2022.08.027933:C(104-113)Online publication date: 14-Oct-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.08.027
Chiarelli NKrnc MMilanič MPferschy UPivač NSchauer J(2022)Fair Allocation of Indivisible Items with Conflict GraphsAlgorithmica10.1007/s00453-022-01079-885:5(1459-1489)Online publication date: 12-Dec-2022
https://dl.acm.org/doi/10.1007/s00453-022-01079-8
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
Garg JHusić EVégh LKhuller SVassilevska Williams V(2021)Approximating Nash social welfare under rado valuationsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451031(1412-1425)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451031
Cicalese FLaber E(2021)On the star decomposition of a graph: Hardness results and approximation for the max–min optimization problemDiscrete Applied Mathematics10.1016/j.dam.2020.07.014289(503-515)Online publication date: Jan-2021
https://doi.org/10.1016/j.dam.2020.07.014
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
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