<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">DEPARTMENT OF COMPUTER SCIENCE<br><br>UNIVERSITY OF CHICAGO<br><br>Date: Friday, February 29, 2008<br>Time: 2:30 p.m.<br>Place: Ryerson 251, 1100 E. 58th Street<br><br>-------------------------------------------------------<br><br>Speaker:<span class="Apple-tab-span" style="white-space: pre; "> </span>Jan Vondrak<br><br>From:<span class="Apple-tab-span" style="white-space: pre; "> </span><span class="Apple-tab-span" style="white-space: pre; "> </span>Princeton University<br><br>Web page:<span class="Apple-tab-span" style="white-space: pre; "> </span><a href="http://www.math.princeton.edu/~jvondrak/">http://www.math.princeton.edu/~jvondrak/</a><br><br>Title: Approximation Algorithms for Combinatorial Allocation Problems<br><br>Abstract: Combinatorial allocation problems arise in situations where <br>a set of items should be distributed among n players in order to <br>maximize a certain social utility function. Such problems have been <br>subject to recent interest due to their applications in combinatorial <br>auctions and electronic commerce. Since allocation problems are <br>typically NP-hard to solve optimally, we seek approximation algorithms <br>that find a solution of value at least c * OPT where OPT is the <br>optimum and c<1 a suitable constant. I will discuss the history of <br>these problems and how they relate to classical work in combinatorial <br>optimization.<br><br>A case of particular interest is the Submodular Welfare Problem where <br>utility functions are assumed to be monotone and submodular, a <br>property known in economics as “diminishing returns”. It has been <br>known that a greedy algorithm yields a ½-approximation for this <br>problem, and more generally for the problem of submodular maximization <br>subject to a matroid constraint [Nemhauser, Wolsey, Fisher ‘78]. Among <br>other results, I will show how this can be improved to a (1-1/e)- <br>approximation – an approximation factor which is known to be optimal. <br>A new ingredient in the algorithm is the approximate solution of a non- <br>linear optimization problem using a “continuous greedy process”.<br><br>------------------------------------------------------<br><br>Host: Laci Babai</body></html>