Amin Saberi

The fair division problem is the problem of dividing resources among entities in an impartial and equitable way. Economists and political economists have given many different formalizations for this notion. There is also a vast literature on this subject in mathematics starting with beautiful results of Steinhaus, Banach and Knaster in 1940's.

In this talk, I will focus on algorithmic questions posed in this context. I will explore interesting connections between the problems in this literature and central problems in approximation algorithms like minimum makespan job scheduling or complexity of finding a Brouwer's fixed point.

The study of some of the problems in fair division literature has resulted in the development of new techniques in approximation algorithms: as a part of our work, I will talk about a message passing method for rounding a fractional matching on a tree.

Monday, April 14, 2008 11:00 AM 315 Upson Hall NOTE TIME AND LOCATION CHANGE		Theory Seminar Spring 2008 CS 789
	Amin Saberi Stanford University
	An Algorithmic Approach to Fair Division
	The fair division problem is the problem of dividing resources among entities in an impartial and equitable way. Economists and political economists have given many different formalizations for this notion. There is also a vast literature on this subject in mathematics starting with beautiful results of Steinhaus, Banach and Knaster in 1940's. In this talk, I will focus on algorithmic questions posed in this context. I will explore interesting connections between the problems in this literature and central problems in approximation algorithms like minimum makespan job scheduling or complexity of finding a Brouwer's fixed point. The study of some of the problems in fair division literature has resulted in the development of new techniques in approximation algorithms: as a part of our work, I will talk about a message passing method for rounding a fractional matching on a tree.