Der Algorithmus von Kruskal für das Finden eines
gewichts-minimalen Spannbaums in einem Graphen \(G = (V,E) \) verfolgt eine
einfache Strategie: wähle Kanten mit geringem Gewicht, solange sie keinen Kreis
schließen. Interessant ist, dass diese gierige (greedy) Wahl von Kanten
immer zu einer optimalen Lösung führt. Der Algorithmus operiert auf der
Menge aller kreis-freien Kantenmengen, die ein Matroid bilden
und der Greedy-Algorithmus lässt sich sofort auf Matroide verallgemeinern.
Auch der Algorithmus von Prim verfolgt eine Greedy-Strategie:
starte von einem fixen Knoten \(v_0 \in V\) und füge günstige Kanten hinzu, die
zu noch unbekannten Knoten führen. Auch dieser Algorithmus findet einen
gewichts-minimalen Spannbaum, aber die unterwegs gefundenen Kantenmengen haben
eine andere Struktur. Es sind genau alle an \(v_0\) gewurzelten Bäume von
\(G\). Diese Menge von partiellen Lösungen ist nicht abgeschlossen unter
Teilmengenbildung, aber trotzdem ist eine Greedy-Strategie optimal!
Die richtige Abstraktion dieses Beispiels sind Greedoide, die in der
Optimierung, aber auch in der Geometrie und Kombinatorik eine große Rolle
spielen. Sowie Matroide den Begriff der 'linearen Unabhängigkeit'
abstrahieren, so abstrahieren Antimatroide den Begriff der 'konvexen
Hülle' aus der Konvexgeometrie und beides sind Beispiele von Greedoiden.
In diesem Seminar wollen wir Greedoide genauer untersuchen, insbesondere aus
der Perspektive von Kombinatorik, Optimierung und Geometrie. Wir halten uns
dabei an das Buch Greedoids von Korte-Lovasz-Schrader.