Technion

Computer Science Colloquium

17/05/2011

Time+Place : Tuesday 17/05/2011 14:30 room 337-8 Taub  Bld.
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

Joint work with Ariel Kulik and Tami Tamir.

Refreshments served from 14:15 on,
Lecture starts at 14:30

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