Universiteit van Amsterdam

Archives

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Speaker: Amin Saberi
Title: Approximation Algorithms for Fair Allocation of Indivisible Goods
Date: Tuesday 3 July 2007
Time: 10:00
Location: CWI, Kruislaan 413, Amsterdam

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 ().

Please note that this newsitem has been archived, and may contain outdated information or links.