difference between intersecting, weakly and crossing supermodular functions

79 Views Asked by At

Am reading some texts on algorithms and I am confused with the differences between these definitions I read in several texts.

Given a set $V$, we have these types of set functions $f:V \rightarrow \mathbb{Z}$

1) Crossing Supermodular: a set function $f$ is crossing supermodular if for every $A,B \subseteq V$ s.t. $A \cap B \neq \emptyset$ and $A \cup B \neq V$, we have:

$$ f(A) + f(B) \leq f(A \cap B) + f(A\cup B) \quad \text{Eq. 1} $$

2) Intersecting Supermodular: a set function $f$ is intersecting supermodular if Eq. $1$ holds whenever $A$ and $B$ are intersecting.

3) Weakly Supermodular: a set function $f$ is weakly supermodular if for every $A,B \subseteq V$, one of the following holds:

$$ f(A) + f(B) \leq f(A \cap B) + f(A \cup B) $$ $$ f(A) + f(B) \leq f(A - B) + f(B-A) $$

I am not sure how these three definitions differ or if $(2)$ and $(3)$ are actually equivalent.. Are there any examples to help me understand these three?