Submodular function

Dependencies:

  1. Set function

$f: 2^{\Omega} \to \mathbb{R}$ be a function. Then $f$ is submodular iff it satisfies one of the following equivalent conditions:

  1. $\forall Y \subseteq \Omega, \forall X \subseteq Y, \forall Z \in \Omega \setminus Y,$ $f(Z \mid X) \ge f(Z \mid Y)$.
  2. $\forall P \subseteq \Omega, \forall Q \subseteq \Omega,$ $f(P) + f(Q) \ge f(P \cup Q) + f(P \cap Q)$.

Proof of equivalence of definitions

Definition 1 implies definition 2 if we let $Y = P$, $X = P \cap Q$ and $Z = Q - P$.

Definition 2 implies definition 1 if we let $P = X \cup Z$ and $Q = Y$.

Dependency for:

  1. Sum of submodular functions is submodular
  2. A set function is additive iff it is submodular and supermodular iff it is subadditive and superadditive.
  3. A submodular function is also a subadditive function
  4. Matroid: rank is submodular
  5. Matroid: weighted rank is submodular
  6. EFX implies EF1
  7. EFX
  8. PROPx

Info:

Transitive dependencies:

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