An approximation algorithm for max-min fair allocation of indivisible goods

11 June 2007

conference paper
Published by Association for Computing Machinery (ACM)

Vol. 39 (7) , 114-121
https://doi.org/10.1145/1250790.1250808

Abstract

In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. The approximation ratio of our algorithm is 1 pk log3 k. As a part of our algorithm, we design an iterative method for rounding a fractional matching on a tree which might be of independent interest.

Keywords

This publication has 7 references indexed in Scilit:

The Santa Claus problem
Published by Association for Computing Machinery (ACM) ,2006
Allocating indivisible goods
ACM SIGecom Exchanges, 2005
On approximately fair allocations of indivisible goods
Published by Association for Computing Machinery (ACM) ,2004
The Probabilistic Method
Published by Wiley ,2000
Cake-Cutting Algorithms
Published by Taylor & Francis ,1998
Fair Division
Published by Cambridge University Press (CUP) ,1996
Approximation algorithms for scheduling unrelated parallel machines
Mathematical Programming, 1990