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 c<1 a suitable constant. I will discuss 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 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)