Sum of submodular functions is submodular

Dependencies:

1. Submodular function

Let $f$ and $g$ be submodular functions. Then $f + g$ is also submodular.

This result can be easily extended to positively weighted sum of multiple functions.

Proof

\begin{align} & (f+g)(P \cup Q) + (f+g)(P \cap Q) \\ &= (f(P \cup Q) + f(P \cap Q)) + (g(P \cup Q) + g(P \cap Q)) \\ &\le (f(P) + f(Q)) + (g(P) + g(Q)) \\ &= (f+g)(P) + (f+g)(Q) \end{align}

Therefore, $f+g$ is also submodular.

Dependency for:

1. Matroid: weighted rank is submodular

Info:

• Depth: 4
• Number of transitive dependencies: 4

Transitive dependencies:

1. /sets-and-relations/countable-set
2. σ-algebra
3. Set function
4. Submodular function