1
$\begingroup$

A few definitions:

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions:

  • for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $
  • for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $

A monotone submodular function is a submodular functions such that for every $ S,T \subseteq E $ with $ S\subseteq T : f(T)\geq f(S) $ . We also define $ f(\emptyset) = 0 $.

Show that $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) $ where $ e_i\in S $ for all i, where f is a monotone submodular function.

2 Answers 2

1

The formula $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) $ is certainly false.If $f$ is a (monotone) submodular function, then $f+c$ with $c \in \mathbb R$ is also a (monotone) submodular function. So you would have $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) + c$ for arbitrary $c \in \mathbb R$, which is obviously not true.

However, it's easy to prove $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) - f(\emptyset) $. Simply note that $f(S)-f(S-\{e_i\}) \leq f(S-U)-f(S-U-\{e_i\})$ for $e_i\notin U$. So the sum is bounded by a telescope sum: $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq \\ (f(S)-f(S-\{e_1\}))+(f(S-\{e_1\}))-f(S-\{e_1, e_2\})+\ldots+(f(S-\cup_{i=1}^{n-1} \{e_i\})-f(S-\cup_{i=1}^n \{e_i\}))\\ =f(S)-f(S-\cup_{i=1}^n \{e_i\}) \leq f(S) - f(\emptyset)$ Only the last step of replacing $f(S-\cup_{i=1}^n \{e_i\})$ by $f(\emptyset)$ requires monotony.

  • 0
    Sorry, forgot to mention that f(empty_set) = 0. You're right of course.2012-12-10
0

Fix a set $E$ with monotone submodular function $f$. Note that $\tilde{f}(I) := f(I) + \lambda$ also will be a monotone submodular function, for any $\lambda \in \mathbb{R}$, since loosely speaking the same number of $\tilde{f}$'s appear on each side of all inequalities.

With that for $n = 1$ our desired inequality just reads $f(S - e_1) \geqslant 0$, but by our analysis this can be taken to be arbitrary, in particular negative.

So perhaps you want some further hypothesis?