3 July 2007, CWI-DIAMANT Seminar Combinatorics and Optimization, Amin Saberi

Abstract

I will talk about the problem of fairly allocating a set of indivisible goods to a set of people from an algorithmic perspective. Fair division has been a central topic in the economic literature and several concepts of fairness have been suggested. I will focus on max-min fairness and envy-freeness criteria.

In particular, I will present an approximation algorithm for the problem of max-min fair allocation of indivisible goods. The approximation ratio of our algorithm is O(\sqr{k} \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.

The talk is based on the following two papers available at http://www.stanford.edu/~saberi:
An approximation algorithm for max-min fair allocation of indivisible goods.
Joint work with Asadpour
On approximately fair allocation of indvisible goods.
Joint work with Lipton, Markakis and Mossel.

For more information, see http://homepages.cwi.nl/~monique/acoseminar/ or contact Vangelis Markakis (V.Markakis at cwi.nl).