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