An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
From MaRDI portal
Publication:5390583
DOI10.1137/080723491zbMath1217.49028OpenAlexW2095794917MaRDI QIDQ5390583
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/a84787d9ff71b066278bc19fc8a93b315f700d02
Linear programming (90C05) Optimality conditions for minimax problems (49K35) Approximation algorithms (68W25) Discrete approximations in optimal control (49M25) Randomized algorithms (68W20)
Related Items (19)
Approximating the Nash Social Welfare with Indivisible Items ⋮ Approximate Maximin Share Allocations in Matroids ⋮ On maximin share allocations in matroids ⋮ A Protocol for Cutting Matroids Like Cakes ⋮ Multistage online maxmin allocation of indivisible entities ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Machine covering in the random-order model ⋮ Online max-min fair allocation ⋮ Fair assignment of indivisible objects under ordinal preferences ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ A Further Analysis of the Dynamic Dominant Resource Fairness Mechanism ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ The efficiency of fair division ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Unnamed Item ⋮ Worst case compromises in matroids with applications to the allocation of indivisible goods ⋮ Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
This page was built for publication: An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
