[Colloquium] Talk by Jan Vondrak, Princeton University on February 29, 2008

[caseyk]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Friday, February 29, 2008
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

-------------------------------------------------------

Speaker:	Jan Vondrak

From:		Princeton University

Web page:	http://www.math.princeton.edu/~jvondrak/

Title: Approximation Algorithms for Combinatorial Allocation Problems

Abstract:  Combinatorial allocation problems arise in situations where  
a set of items should be distributed among n players in order to  
maximize a certain social utility function. Such problems have been  
subject to recent interest due to their applications in combinatorial  
auctions and electronic commerce. Since allocation problems are  
typically NP-hard to solve optimally, we seek approximation algorithms  
that find a solution of value at least c * OPT where OPT is the  
optimum and c<1 a suitable constant. I will discuss the history of  
these problems and how they relate to classical work in combinatorial  
optimization.

A case of particular interest is the Submodular Welfare Problem where  
utility functions are assumed to be monotone and submodular, a  
property known in economics as “diminishing returns”. It has been  
known that a greedy algorithm yields a ½-approximation for this  
problem, and more generally for the problem of submodular maximization  
subject to a matroid constraint [Nemhauser, Wolsey, Fisher ‘78]. Among  
other results, I will show how this can be improved to a (1-1/e)- 
approximation – an approximation factor which is known to be optimal.  
A new ingredient in the algorithm is the approximate solution of a non- 
linear optimization problem using a “continuous greedy process”.

------------------------------------------------------

Host: Laci Babai