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:𝒫(S)\to ℝ$ heißt submodular, wenn für alle $T,U\subseteq S$ gilt, dass

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

Beispiel

Sei $A\in {ℝ}^{m\times n}$. Dann ist die Funktion $f:𝒫(\{1,\dots ,n\})\to ℝ$, die jeder Menge von Spaltenindizes die Dimension des von den entsprechenden Spalten von $A$ aufgespannten Vektorraumes zuordnet, submodular.

Eigenschaften

Sei $f:𝒫(S)\to ℝ$. Dann sind die folgenden Aussagen äquivalent:

• $f$ ist submodular
• $f(T\cup \{s\})-f(T)\ge f(U\cup \{s\})-f(U)$ für alle $s\in S\mathrm{\setminus }U$ und $T,U\subseteq S$ mit $T\subseteq U$
• $f(U\cup \{s\})+f(U\cup \{t\})\ge 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,\dots ,n\}$ und $f:𝒫(S)\to ℝ$ eine Mengenfunktion. Dann heißt die Menge

$E{P}_f:=\{x\in {ℝ}^n\mid \sum _{j\in U}{x}_j\le f(U)\text{ für alle }U\subset S\}$

das erweiterte Polymatroid zu $f$. Wenn $f$ submodular ist und $f(\mathrm{\varnothing })=0$, kann das Minimum einer linearen Funktion über $E{P}_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 $E{P}_f$ ganzzahlig, so dass auch eine ganzzahlige Lösung effizient berechnet werden kann.

Literatur

• Vorlage:Literatur