The University of Michigan Combinatorics Seminar


Abstract 

Combinatorial allocation problems have been a subject of recent interest due to their role in online 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 NPhard 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 (11/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/2approximation. The optimal (11/e)approximation can be extended to a more general problem for which a 1/2approximation 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 nonlinear 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. 