This paper gives two definitions of Submodular Function. Let $N$ be the base set, and let $\mathcal P(N)$ denote the powerset of $N$.

Definition 1: A function $z: \mathcal P(N) \to \mathbb R^+$ is a nondecreasing submodular function if $z(A) + z(B) \ge z(A \cup B) + z(A \cap B)$.

Now, for $j \in N$ and $S \subset N$, define $\rho_j(S) = z(S \cup \{j\}) - z(S)$

Definition 2: A function $z: \mathcal P(N) \to \mathbb R^+$ is submodular and nondecreasing iff either

  1. $\rho_j(S) \ge \rho_j(T) \ge 0$ $\qquad \forall S \subseteq T \subseteq N\qquad $ or
  2. $z(T) \le z(S) + \sum_{j \in T \setminus S} \rho_j(S)$ $\qquad \forall S, T \subseteq N$

How do I prove that the two definitions are equivalent? I have tried plugging in different types of sets (like $A, B$ such that $A \subseteq B$) in both definitions, but no luck.


You can find a solution to this on Page Number 420-421 of the following book on Submodular Functions. here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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