Combinatorial algorithm for restricted max-min fair allocation

DOI10.1145/3070694MaRDI QIDQ4962664zbMATH OpenOpenAlexFDO

Authors Christos Kalaitzis, Ola Svensson, Chidambaram Annamalai

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.0607

zbMATH Keywords

approximation algorithmsefficient local searchfair allocation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: 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 certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of $4+epsilon$. In contrast, however, the best known approximation algorithm for the problem has an unspecified large constant guarantee. In this paper we significantly narrow this gap by giving a $13$-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [Hax95] for hypergraph matchings, and later used in this context by Asadpour, Feige, and Saberi [AFS12]. 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.

Recommendations

• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Quasi-polynomial local search for restricted max-min fair allocation
• Quasi-polynomial local search for restricted max-min fair allocation
• Restricted max-min allocation: integrality gap and approximation algorithm
• Restricted Max-Min Fair Allocation

Cited in

(25)

• An efficient primal-dual algorithm for fair combinatorial optimization problems
• Restricted max-min allocation: integrality gap and approximation algorithm
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
• Multistage online maxmin allocation of indivisible entities
• Fair and efficient allocation with few agent types, few item types, or small value levels
• General max-min fair allocation
• Fair allocation of indivisible items with conflict graphs
• Quasi-polynomial local search for restricted max-min fair allocation
• Quasi-polynomial local search for restricted max-min fair allocation
• Restricted Max-Min Fair Allocation
• Fair Packing of Independent Sets
• Restricted max-min allocation: approximation and integrality gap
• Local search breaks 1.75 for graph balancing
• A quasi-polynomial approximation for the restricted assignment problem
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Polynomial-time combinatorial algorithm for general max-min fair allocation
• Better trees for Santa Claus
• A geometric programming approach to solve the restricted assignment case of the Santa Claus problem
• Improved integrality gap in max-min allocation, or, topology at the north pole
• The submodular Santa Claus problem in the restricted assignment case
• Additive approximation schemes for load balancing problems
• Almost envy-free allocation of indivisible goods: a tale of two valuations
• Parameterized hardness results for the \textsc{Restricted Santa Claus Problem}
• A combinatorial algorithm to establish a fair border

This page was built for publication: Combinatorial algorithm for restricted max-min fair allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962664)