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.