Approximation Algorithms for Combinatorial Allocation Problems

Computer Science Colloquium: Approximation Algorithms for Combinatorial Allocation ProblemsSpeaker: Dr. Jan Vondrak (Princeton)Time: 3:30 pm - 5:00 pmDate: Jan 29, 2008Location: SSL 150Host: Prof. David KempeABSTRACT: 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 * OPTwhere OPT is the optimum and cA particular case of interest is the Submodular Welfare Problem where utility functions are assumed to be monotone and submodular. It has been known since 1978 that a greedy algorithm gives a 1/2-approximation [Nemhauser,Wolsey,Fisher] for a more general problem of submodular maximization subject to a matroid constraint. 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 technique that we use is the approximate solution of a non-linear optimization problem using a "continuous greedy algorithm".(partly joint work with G. Calinescu, C. Chekuri and M. Pal)BIO: Jan Vondrak grew up in the Czech republic and received a Master's degree in computerscience from Charles University in Prague. He attended graduate school at MIT where he received a PhD in applied math in 2005. His advisor was Michel Goemans. He spent a year as a postdoctoral researcher at Microsoft Reserch (2005-06) and is currently a postdoctoral researcher at Princeton University.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Georgia Lum