Editing Supermodular function (section)

==Supermodular set functions==
Supermodularity can also be defined for [[Set function|set functions]], which are functions defined over subsets of a larger set. Many properties of [[Submodular set function|submodular set functions]] can be rephrased to apply to supermodular set functions.

Intuitively, a supermodular function over a set of subsets demonstrates "increasing returns". This means that if each subset is assigned a real number that corresponds to its value, the value of a subset will always be less than the value of a larger subset which contains it. Alternatively, this means that as we add elements to a set, we increase its value.

=== Definition ===
Let <math>S</math> be a finite set. A set function <math>f: 2^S \to \mathbb{R}</math> is '''supermodular''' if it satifies the following (equivalent) conditions:<ref>{{Citation |last=McCormick |first=S. Thomas |title=Discrete Optimization |chapter=Submodular Function Minimization |date=2005 |series=Handbooks in Operations Research and Management Science |volume=12 |pages=321–391 |chapter-url=https://linkinghub.elsevier.com/retrieve/pii/S0927050705120076 |access-date=2024-12-12 |publisher=Elsevier |language=en |doi=10.1016/s0927-0507(05)12007-6 |isbn=978-0-444-51507-0}}</ref>

# <math> f(A)+f(B) \leq f(A \cap B) + f(A \cup B) </math> for all <math> A, B \subseteq S </math>.
# <math> f(A \cup \{v\}) - f(A) \leq f(B \cup \{v\}) - f(B) </math> for all <math> A \subset B \subset V </math>, where <math> v \notin B </math>.

A set function <math>f</math>  is submodular if <math>-f</math> is supermodular, and modular if it is both supermodular and submodular.

=== Additional Facts ===

* If <math> f </math> is modular and <math> g </math> is submodular, then <math> f-g </math> is a supermodular function.
* A non-negative supermodular function is also a superadditive function.