Submodulare Funktion

Sei ${\displaystyle S}$ eine Menge. Eine Mengenfunktion ${\displaystyle f\colon {\mathcal {P}}(S)\to \mathbb {R} }$ heißt submodular, wenn für alle ${\displaystyle T,U\subseteq S}$ gilt, dass

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

Sei ${\displaystyle A\in \mathbb {R} ^{m\times n}}$. Dann ist die Funktion ${\displaystyle f\colon {\mathcal {P}}(\{1,\dotsc ,n\})\to \mathbb {R} }$, die jeder Menge von Spaltenindizes die Dimension des von den entsprechenden Spalten von ${\displaystyle A}$ aufgespannten Vektorraumes zuordnet, submodular.

Sei ${\displaystyle f\colon {\mathcal {P}}(S)\to \mathbb {R} }$. Dann sind die folgenden Aussagen äquivalent:

• ${\displaystyle f}$ ist submodular
• ${\displaystyle f(T\cup \{s\})-f(T)\geq f(U\cup \{s\})-f(U)}$ für alle ${\displaystyle s\in S\backslash U}$ und ${\displaystyle T,U\subseteq S}$ mit ${\displaystyle T\subseteq U}$
• ${\displaystyle f(U\cup \{s\})+f(U\cup \{t\})\geq f(U)+f(U\cup \{s,t\})}$ für alle ${\displaystyle U\subseteq S}$ und alle ${\displaystyle s,t\in S}$.

Sei ${\displaystyle S=\{1,\dotsc ,n\}}$ und ${\displaystyle f\colon {\mathcal {P}}(S)\to \mathbb {R} }$ eine Mengenfunktion. Dann heißt die Menge

${\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\}}$

das erweiterte Polymatroid zu ${\displaystyle f}$. Wenn ${\displaystyle f}$ submodular ist und ${\displaystyle f(\emptyset )=0}$, kann das Minimum einer linearen Funktion über ${\displaystyle EP_{f}}$ mit einem Greedy-Algorithmus in Zeit polynomial in ${\displaystyle n}$ gefunden werden. Nimmt ferner ${\displaystyle f}$ nur ganzzahlige Werte an, so sind sämtliche Ecken von ${\displaystyle EP_{f}}$ ganzzahlig, so dass auch eine ganzzahlige Lösung effizient berechnet werden kann.

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