Sub-modular function

A submodular function is a set function that generalizes the rank function of a matroid . Submodular functions play an important role in combinatorial optimization .

definition

Be a lot. A set function is called submodular if it holds for all that ${\displaystyle S}$ ${\displaystyle f\colon {\mathcal {P}}(S)\to \mathbb {R} }$ ${\displaystyle T,U\subseteq S}$

${\displaystyle f(T\cap U)+f(T\cup U)\leq f(T)+f(U)}$

example

Be . Then the function which assigns the dimension of the vector space spanned by the corresponding columns of to each set of column indices is submodular. ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle f\colon {\mathcal {P}}(\{1,\dotsc ,n\})\to \mathbb {R} }$ ${\displaystyle A}$

properties

Be . Then the following statements are equivalent: ${\displaystyle f\colon {\mathcal {P}}(S)\to \mathbb {R} }$

• ${\displaystyle f}$ is submodular
• ${\displaystyle f(T\cup \{s\})-f(T)\geq f(U\cup \{s\})-f(U)}$for everyone and with ${\displaystyle s\in S\backslash U}$ ${\displaystyle T,U\subseteq S}$ ${\displaystyle T\subseteq U}$
• ${\displaystyle f(U\cup \{s\})+f(U\cup \{t\})\geq f(U)+f(U\cup \{s,t\})}$for everyone and everyone . ${\displaystyle U\subseteq S}$ ${\displaystyle s,t\in S}$

Application in combinatorial optimization

Let and be a set function. Then the amount is called ${\displaystyle S=\{1,\dotsc ,n\}}$ ${\displaystyle f\colon {\mathcal {P}}(S)\to \mathbb {R} }$

${\displaystyle EP_{f}:=\{x\in \mathbb {R} ^{n}\mid \sum _{j\in U}x_{j}\leq f(U){\text{ für alle }}U\subset S\}}$

the expanded polymatroid too . If is submodular and , the minimum of a linear function can be found in polynomial in time using a greedy algorithm . Furthermore, if only integer values ​​are assumed, then all vertices are of integers, so that an integer solution can also be calculated efficiently. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f(\emptyset )=0}$ ${\displaystyle EP_{f}}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle EP_{f}}$

literature

• Alexander Schrijver: Combinatorial Optimization . Polyhedra and Efficiency. Springer, Berlin 2003, ISBN 3-540-44389-4 .