Wie grundlegend sind Matroiden und Gieroide im Algorithmus -Design?

Question

Anfänglich, Matroiden wurden eingeführt, um die Begriffe der linearen Unabhängigkeit einer Sammlung von Untergruppen $ e $ über einige Bodenset $ i $ zu verallgemeinern. Bestimmte Probleme, die diese Struktur enthalten, ermöglichen gierige Algorithmen, optimale Lösungen zu finden. Das Konzept von Gieroide wurde später eingeführt, um diese Struktur zu verallgemeinern, um mehr Probleme zu erfassen, die es ermöglichen, optimale Lösungen durch gierige Methoden zu finden.

Wie oft entstehen diese Strukturen im Algorithmus -Design?

Darüber hinaus kann ein gieriger Algorithmus meistens nicht in der Lage sein, das zu erfassen, was erforderlich ist, um optimale Lösungen zu finden, sondern möglicherweise immer noch sehr gute ungefähre Lösungen (beispielsweise Packung). Gibt es eine Möglichkeit, zu messen, wie "eng" ein Problem für einen Gier oder eine Matroid ist?

Answer 1

Es ist schwierig, die Frage "wie oft" zu beantworten. Aber wie bei allen "zugrunde liegenden Strukturen" entsteht der Nutzen aus der Erkenntnis, dass das zugrunde liegende Problem, das man zu lösen versucht, eine Matroid- (oder Greedoid-) Struktur hat. Es sind nicht nur Matroid -Probleme. Das Problem der Matroid -Schnittpunkte hat ein spezifisches Modell (partitale Matching).

Nick Harvey hat seine Doktorarbeit gemacht Zeige kürzlich auf Algorithmen für Matroidprobleme und untersuchte auch die optimierte Submodularfunktion (die Matroidprobleme verallgemeinert). Das Lesen der Einführung und des Hintergrunds in die These kann hilfreich sein.