CS Colloquia: Approximation algorithms for combinatorial allocation problems

Title: Approximation algorithms for combinatorial allocation problemsSpeaker: Dr. Jan Vondrak (Princeton)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 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:
I grew up in the Czech republic and I got a Master's degree in computer
science from Charles University in Prague. Then I went to grad school at MIT
where I got a PhD in applied math in 2005. My advisor was Michel Goemans. I
spent a year as a postdoc at Microsoft Reserch (2005-06) and currently I'm a
postdoc at Princeton University.
~

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia