Submodulare Funktion

Eine submodulare Funktion ist eine Mengenfunktion, die die Rangfunktion eines Matroids verallgemeinert. Submodulare Funktionen spielen in der kombinatorischen Optimierung eine wichtige Rolle.

Definition

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

$f(T\cap U)+f(T\cup U)\leq f(T)+f(U)$

Beispiel

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

Eigenschaften

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

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

Anwendung in der kombinatorischen Optimierung

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

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

Literatur

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