Wie grundlegend sind Matroiden und Greedoiden im Algorithmus-Design?

23

Anfänglich wurden Matroiden eingeführt, um die Begriffe der linearen Unabhängigkeit einer Sammlung von Teilmengen über eine Grundmenge I zu verallgemeinern . Bestimmte Probleme, die diese Struktur enthalten, ermöglichen es gierigen Algorithmen, optimale Lösungen zu finden. Das Konzept der Greedoiden wurde später eingeführt, um diese Struktur zu verallgemeinern und mehr Probleme zu erfassen, die es ermöglichen, mit gierigen Methoden optimale Lösungen zu finden.Eich

Wie oft entstehen diese Strukturen im Algorithmusdesign?

Darüber hinaus kann ein gieriger Algorithmus häufig nicht vollständig erfassen, was für die Suche nach optimalen Lösungen erforderlich ist, kann aber dennoch sehr gute Näherungslösungen finden (z. B. Bin Packing). In Anbetracht dessen, gibt es eine Möglichkeit zu messen, wie "nah" ein Problem an einem Greedoid oder einer Matroid ist?

Nicholas Mancuso
quelle

Antworten:

18

Es ist schwierig, die Frage "wie oft" zu beantworten. Aber wie bei allen "zugrunde liegenden Strukturen" besteht der Vorteil darin, zu erkennen, dass das zugrunde liegende Problem, das man zu lösen versucht, eine matroide (oder gierige) Struktur hat. Es sind nicht nur Matroid-Probleme. Das Matroid-Schnittpunktproblem hat ein spezifisches Modell (bipartite matching).

Nick Harvey promovierte kürzlich über Algorithmen für Probleme mit der Matroidfunktion und beschäftigte sich auch mit der Optimierung der submodularen Funktion (die Probleme mit der Matroidfunktion verallgemeinert). Es kann hilfreich sein, die Einleitung und den Hintergrund der Arbeit zu lesen.

Suresh
quelle
4
Ich möchte nur einen Hinweis zum Thema "Nähe" hinzufügen. Wenn ein gieriger Algorithmus eine k-Approximation ergibt, kann das Problem als k-Matroid strukturiert sein.
Nicholas Mancuso
+1. Gute Antwort. Ich frage mich, warum die These besagt, dass eine submodulare Funktion eine Verallgemeinerung oder Zusammenfassung einer Matroid ist. Die einzige Verbindung, die ich zwischen den beiden finden kann, ist der Rang eines Submatroids in einer Teilmenge, und zwar eine submodulare Funktion.
Tim
2
Es gibt eine sehr elegante geometrische Verbindung. Um dies besser zu verstehen, sollten Sie sich bei en.wikipedia.org/wiki/Polymatroid umsehen . Wenn das mit einer submodularen Funktion verknüpfte Polytop bestimmte Eigenschaften hat, erhalten Sie ungefähr eine Matroide. Weitere Informationen hierzu finden Sie in Satoru Fujishiges Buch: kurims.kyoto-u.ac.jp/~fujishig/Book1a.html
Suresh
4
Wie in CLRS (Seite 437 der 3nd Edition) angegeben, die Matroidtheorie nicht das Aktivität-Auswahl Problem und das Huffman - Kodierung Problem abdecken. Deckt die Greedoid-Theorie sie ab?
Hengxin