[Colloquium] Reminder: Talk by Jan Vondrak, Princeton University, Today

[caseyk]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Friday, February 29, 2008
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

-------------------------------------------------------

Speaker:	Jan Vondrak

From:		Princeton University

Web page:	http://www.math.princeton.edu/~jvondrak/

Title: Approximation Algorithms for Combinatorial Allocation Problems

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 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 ½-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”.

------------------------------------------------------

Host: Laci Babai
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080229/2ef03e78/attachment.html