Eine submodulare Funktion ist eine Mengenfunktion, die die Rangfunktion eines Matroids verallgemeinert. Submodulare Funktionen spielen in der kombinatorischen Optimierung eine wichtige Rolle.
Definition Sei eine Menge. Eine Mengenfunktion heißt submodular, wenn für alle gilt, dass
Beispiel Sei . Dann ist die Funktion , die jeder Menge von Spaltenindizes die Dimension des von den entsprechenden Spalten von aufgespannten Vektorraumes zuordnet, submodular.
Eigenschaften Sei . Dann sind die folgenden Aussagen äquivalent: ist submodular für alle und mit für alle und alle .
Anwendung in der kombinatorischen Optimierung 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
Kategorie:Kombinatorische Optimierung Kategorie:Mathematische Funktion