On Allocating Goods to Maximize Fairness

DOI10.1109/FOCS.2009.51zbMath1292.91102MaRDI QIDQ5171208

Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (29)

Approximating the Nash Social Welfare with Indivisible Items ⋮ Restricted max-min allocation: integrality gap and approximation algorithm ⋮ A truthful constant approximation for maximizing the minimum load on related machines ⋮ Parameterized orientable deletion ⋮ Multistage online maxmin allocation of indivisible entities ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ On the configuration LP for maximum budgeted allocation ⋮ Online max-min fair allocation ⋮ Unnamed Item ⋮ Polynomial-time combinatorial algorithm for general max-min fair allocation ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ General max-min fair allocation ⋮ Structural parameters for scheduling with assignment restrictions ⋮ 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 ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Restricted Max-Min Fair Allocation ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ The efficiency of fair division ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On \((1, \epsilon )\)-restricted max-min fair allocation problem ⋮ Unnamed Item ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Nash Social Welfare, Matrix Permanent, and Stable Polynomials ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

This page was built for publication: On Allocating Goods to Maximize Fairness