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[Bearbeiten | Quelltext bearbeiten]
Sei eine Menge. Eine Mengenfunktion heißt submodular, wenn für alle gilt, dass
Beispiel[Bearbeiten | Quelltext bearbeiten]
Sei . Dann ist die Funktion , die jeder Menge von Spaltenindizes die Dimension des von den entsprechenden Spalten von aufgespannten Vektorraumes zuordnet, submodular.
Eigenschaften[Bearbeiten | Quelltext bearbeiten]
Sei . Dann sind die folgenden Aussagen äquivalent:
- ist submodular
- für alle und mit
- für alle und alle .
Anwendung in der kombinatorischen Optimierung[Bearbeiten | Quelltext bearbeiten]
Sei und eine Mengenfunktion. Dann heißt die Menge
das erweiterte Polymatroid zu . Wenn submodular ist und , kann das Minimum einer linearen Funktion über mit einem Greedy-Algorithmus in Zeit polynomial in gefunden werden. Nimmt ferner nur ganzzahlige Werte an, so sind sämtliche Ecken von ganzzahlig, so dass auch eine ganzzahlige Lösung effizient berechnet werden kann.
Literatur[Bearbeiten | Quelltext bearbeiten]
- Alexander Schrijver: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Berlin 2003, ISBN 3-540-44389-4.