Combinatorial Algorithm for Restricted Max-Min Fair Allocation

DOI10.1145/3070694zbMath1446.91043arXiv1409.0607OpenAlexW2168581227MaRDI QIDQ4962664

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 algorithmsfair allocationefficient local search

Mathematics Subject Classification ID

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

Related Items (15)

Fair Packing of Independent Sets ⋮ Restricted max-min allocation: integrality gap and approximation algorithm ⋮ Multistage online maxmin allocation of indivisible entities ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Polynomial-time combinatorial algorithm for general max-min fair allocation ⋮ A note on the integrality gap of the configuration LP for restricted Santa Claus ⋮ General max-min fair allocation ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Fair allocation of indivisible items with conflict graphs ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ A Quasi-Polynomial Approximation for the Restricted Assignment Problem ⋮ Restricted Max-Min Fair Allocation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Better trees for Santa Claus

This page was built for publication: Combinatorial Algorithm for Restricted Max-Min Fair Allocation