The University of Michigan Combinatorics Seminar
Fall 2007
December 7, 4:10-5:00, 3866 East Hall

Approximation algorithms for combinatorial allocation problems

Jan Vondrák

Princeton University


Combinatorial allocation problems have been a subject of recent interest due to their role in on-line auctions and electronic commerce. An allocation problem entails a finite set of "items" that should be distributed among participating "players" in order to maximize a certain "social utility" function. Since such problems are typically NP-hard to solve optimally, we seek approximation algorithms that find a solution comparable to an optimum one. The approximation that one can achieve depends on what conditions we impose on the utility functions and how these functions are accessible. I will describe the history of these problems and how they relate to more classical work in combinatorial optimization.

A particular case of interest is the Submodular Welfare Problem, where the utility functions are assumed to be submodular, a property that is known in economics as "diminishing returns". Our recent result is that a (1-1/e)-approximation can be achieved for this problem. It has been known that a better approximation is impossible unless P=NP, but the best known algorithm achieved only a 1/2-approximation. The optimal (1-1/e)-approximation can be extended to a more general problem for which a 1/2-approximation was also known [Fisher, Nemhauser, Wolsey '78]. I will discuss this, related results, and the techniques that we use - randomization, replacing the discrete problem by a continuous one, and approximately solving a non-linear optimization problem using a variant of the gradient descent method.

Some of these results were obtained in collaborations with Uri Feige, with Vahab Mirrokni, and with Gruia Calinescu, Chandra Chekuri and Martin Pal.