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 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 Front Desk