Supermodular function
From Egres Open
If [math]p:2^V \to {\mathbb R} \cup \{-\infty\}[/math] is a set function on a finite ground set V, and [math]X,Y \subseteq V[/math], then we define the following two inequalities:
- supermodular inequality: [math]p(X)+p(Y) \leq p(X \cap Y)+p(X \cup Y)[/math]
- negamodular inequality: [math]p(X)+p(Y) \leq p(X \setminus Y)+p(Y \setminus X)[/math]
We can define several classes of set functions based on where these inequalities hold:
- p is (fully) supermodular if the supermodular inequality holds for every [math]X,Y \subseteq V[/math]. In other words, p is supermodular if and only if -p is a submodular function.
- p is negamodular if the negamodular inequality holds for every [math]X,Y \subseteq V[/math].
- p is skew-supermodular if for every [math]X,Y \subseteq V[/math] either the supermodular or the negamodular inequality holds.
- p is intersecting supermodular if the supermodular inequality holds for every [math]X,Y \subseteq V[/math] for which [math]X \cap Y \neq \emptyset[/math].
- p is crossing supermodular if the supermodular 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]. We can similarly define crossing negamodular functions, too.
See Frank and Király [1] for a survey on covering problems related to supermodular functions.
