[Colloquium] Jan Vondrak, Princeton University- TTI-C Talk

[Julia MacGlashan]

When:             Thursday, February 28, 2008 @ 10:00 am

 

Where:            TTI-C Conference Room

 

Who:               Jan Vondrak, Princeton University

 

Topic:             Approximation algorithms for combinatorial allocation
problems

 

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 classical work in
combinatorial optimization.

 

A case of particular interest is the Submodular Welfare Problem where
utility functions are assumed to be monotone and submodular, a property
known in economics as "diminishing returns". It has been known that a greedy
algorithm yields a 1/2-approximation for this problem, and more generally
for the problem of submodular maximization subject to a matroid constraint
[Nemhauser, Wolsey, Fisher '78]. Among other results, 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 ingredient in the algorithm is the approximate
solution of a non-linear optimization problem using a "continuous greedy
process".

 

Contact:          Julia Chuzhoy, TTI-C         cjulia at tti-c.org
773-834-2490

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080226/4f5a12b0/attachment.html