Combinatorial Algorithm for Restricted Max-Min Fair Allocation

DOI10.1137/1.9781611973730.90MaRDI QIDQ5363005zbMATH OpenOpenAlexFDO

Authors Christos Kalaitzis, Ola Svensson, Chidambaram Annamalai

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.90

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)

Recommendations

• Combinatorial algorithm for restricted max-min fair allocation
• Restricted Max-Min Fair Allocation
• On \((1, \epsilon )\)-restricted max-min fair allocation problem
• Restricted max-min fair allocations with inclusion-free intervals
• An approximation algorithm for max-min fair allocation of indivisible goods
• On (1,)-restricted max-min fair allocation problem
• General max-min fair allocation
• An algorithm for the fair resource allocation problem with a submodular constraint
• An algorithm for identifying fair and optimal allocations
• Fair allocation algorithms for indivisible items under structured conflict constraints

Cited in

(15)

• An efficient primal-dual algorithm for fair combinatorial optimization problems
• Restricted max-min allocation: integrality gap and approximation algorithm
• Quasi-polynomial local search for restricted max-min fair allocation
• Approximating the Nash Social Welfare with Indivisible Items
• A further analysis of the dynamic dominant resource fairness mechanism
• Quasi-polynomial local search for restricted max-min fair allocation
• Combinatorial algorithm for restricted max-min fair allocation
• Restricted Max-Min Fair Allocation
• Restricted max-min allocation: approximation and integrality gap
• Lazy local search meets machine scheduling
• Compact LP relaxations for allocation problems
• Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
• On min-max graph balancing with strict negative correlation constraints
• On \((1, \epsilon )\)-restricted max-min fair allocation 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 Q5363005)