Submodular function

Let V be a finite ground set. A set function [math]b:2^V \to {\mathbb R} \cup \{\infty\}[/math] is (fully) submodular if [math]b(X)+b(Y) \geq b(X \cap Y)+b(X \cup Y)[/math] for every [math]X,Y \subseteq V[/math]. In other words, b is submodular if and only if -b is a supermodular function.

Intersecting and crossing submodular set functions can be defined similarly as their supermodular counterparts:

• p is intersecting submodular if the submodular inequality holds for every [math]X,Y \subseteq V[/math] for which [math]X \cap Y \neq \emptyset[/math].
• p is crossing submodular if the submodular inequality holds for every [math]X,Y \subseteq V[/math] for which [math]X \cap Y \neq \emptyset[/math] and [math]X \cup Y \neq V[/math].
• p is posimodular if -p is negamodular.