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, for any $ S,T\subseteq E : f(T)\leq f(S) + \sum_{e_i\in T-S}(f(S\cup\{e_i\})-f(S)) $ where $f$ is a submodular monotone function . I've tried induction but got no where.

1 Answers 1

1

Consider $f(S \cup \{e_i\})+f(S \cup \{e_j\} ), e_i,e_j \in T-S$. It is obvious that $e_i,e_j \notin S $. So, $f(S \cup \{e_i\})+f(S \cup \{e_j\} ) \geq f(S \cup \{e_i,e_j\})+f(S)$ Extending it to three terms, $f(S \cup \{e_i\})+f(S \cup \{e_j\} )+f(S \cup \{e_k\}) \geq f(S\cup\{e_i,e_j\})+f(S\cup \{e_k\}) + f(S) \geq f(S \cup\{e_i,e_j,e_k\}) +2f(S)$

Suppose $|T-S| = n$. Then, $\sum_{i \in T-S} f(S\cup \{e_i\}) \geq f(S \cup \{\cup e_i\}) + (n-1)f(S)$ $\sum_{i \in T-S} (f(S\cup \{e_i\})-f(S)) \geq f(S \cup \{\cup_{i\in T-S} e_i\}) -f(S)$ $f(S)+\sum_{i \in T-S} (f(S\cup \{e_i\})-f(S)) \geq f(S \cup \{\cup_{i\in T-S} e_i\}) $ Note that $f(S \cup \{\cup_{i\in T-S} e_i\}) = f(S\cup T)$

$f(S)+\sum_{i \in T-S} (f(S\cup \{e_i\})-f(S)) \geq f(S \cup T)\geq f(T)$

There you go!!

  • 0
    Sorry, computer broke :) Thanks for your answer2012-12-11