Technion Computer Science Colloquium 17/05/2011 Time+Place : Tuesday 17/05/2011 14:30 room 337-8 Taub Bld. Speaker : Hadas Shachnai Affiliation: Computer Science Department, Technion Title : Maximizing Submodular Set Functions Subject to Multiple Linear Constraints Abstract : The concept of submodularity plays a vital role in combinatorial optimization. In particular, many important optimization problems can be cast as submodular maximization problems, including maximum coverage, maximum facility location and max cut in directed/undirected graphs. We consider the problem of maximizing a submodular set function subject to $d$ linear constraints, where $d > 1$ is some constant. We present the first known approximation algorithms for monotone functions, which yield a nearly optimal ratio of $(1-e^{-1}-\eps)$. For arbitrary submodular functions, we improve the best known bound to $1/4 - \eps$, for any $\eps > 0$. Our approximation technique relies on the strong relation that we establish between the discrete problem and its continuous relaxation. Formally, we show that, for any non-negative submodular function, an $\alpha$-approximation algorithm for the continuous relaxation implies a randomized $(\alpha - \eps)$-approximation algorithm for the discrete problem. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial size domain. This leads to a deterministic version of the technique. Our approach has a potential of wider applicability, which we demonstrate on the examples of the Generalized Assignment Problem and Maximum Coverage with additional linear constraints. Joint work with Ariel Kulik and Tami Tamir. Refreshments served from 14:15 on, Lecture starts at 14:30 ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>