Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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!!

share|improve this answer
    
Sorry, computer broke :) Thanks for your answer –  Shmoopy Dec 11 '12 at 18:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.