Funciones monótonas submodulares

Question

Algunas definiciones:

Una función submodular $ f:2^E \rightarrow R $ es una función que satisface las dos definiciones equivalentes siguientes:

• por cada $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $
• por cada $ S,T\subseteq E $ con $ S\subseteq T $ y para cada $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $

Una función submodular monótona es una función submodular tal que para cada $ S,T \subseteq E $ con $ S\subseteq T : f(T)\geq f(S) $ . También definimos $ f(\emptyset) = 0 $ .

Demuestre que, para cualquier $ S,T\subseteq E : f(T)\leq f(S) + \sum_{e_i\in T-S}(f(S\cup\{e_i\})-f(S)) $ donde $f$ es una función submodular monótona . He intentado la inducción pero no he conseguido nada.

Answer 1

Considere $f(S \cup \{e_i\})+f(S \cup \{e_j\} ), e_i,e_j \in T-S$ . Es evidente que $e_i,e_j \notin S $ . Así que, $$f(S \cup \{e_i\})+f(S \cup \{e_j\} ) \geq f(S \cup \{e_i,e_j\})+f(S)$$ Ampliándolo a tres mandatos, $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)$

Supongamos que $|T-S| = n$ . Entonces, $$\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\}) $$ Tenga en cuenta que $$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)$$

¡¡Ahí tienes!!