##### Department of Mathematics,

University of California San Diego

****************************

### Special Colloquium

## Jan Vondrak

#### Princeton University

## Approximation algorithms for combinatorial allocation problems

##### Abstract:

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. A particular case of interest is the Submodular Welfare Problem, where the utility functions are assumed to be submodular. Our recent result is that a $(1-1/e)$-approximation can be achieved for the Submodular Welfare Problem, which is known to be optimal. The $(1-1/e)$-approximation can be extended to a more general problem for which a $1/2$-approximation was known since 1978 [Fisher,Nemhauser,Wolsey]. I will discuss our improvements 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 continuous greedy method. Partly joint work with G. Calinescu, C. Chekuri and M. Pal.

Hosts: Sam Buss and Fan Chung Graham

### December 3, 2007

### 1:00 PM

### AP&M 6402

****************************