Approximation Algorithms for Computing Maximin Share Allocations

DOI10.1007/978-3-662-47672-7_4zbMath1409.68327OpenAlexW2776361207MaRDI QIDQ3448772

Georgios Amanatidis, Afshin Nikzad, Evangelos Markakis, Amin Saberi

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: http://repository.essex.ac.uk/27279/1/journal-mms_acm_alt.pdf

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (9)

Approximating the Nash Social Welfare with Indivisible Items ⋮ Asymptotic existence of proportionally fair allocations ⋮ Approximate Maximin Share Allocations in Matroids ⋮ On maximin share allocations in matroids ⋮ Asymptotic existence of fair divisions for groups ⋮ The fair division of hereditary set systems ⋮ Maximin share guarantee for goods with positive externalities ⋮ Approximate maximin shares for groups of agents ⋮ Local fairness in hedonic games via individual threshold coalitions

Cites Work

• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• On the complexity of cake cutting
• The Santa Claus problem
• Fair Enough
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation Algorithms for Computing Maximin Share Allocations