Eine obere Grenze der Approximationsrate für den Greedy-Algorithmus für die gesetzte Deckung (einzelne Instanzen)

Question

Ungewollt habe ich eine Möglichkeit, eine obere Grenze des Approximationsverhältnisses für den Greedy-Algorithmus zu finden (und zu beweisen), die (die Grenze) sein kann für einzelne Instanzen des Set-Cover-Problems erhalten. Für Probleme, die ich in meiner Bibliothek habe, ist diese Grenze des Verhältnisses besser als die Werte, die wir mit bekannten Formeln für den allgemeinen Fall des Problems erhalten können.

Ob es irgendwie verwendet werden kann? Oder ist es ein nutzloses Ergebnis?

Answer 1

Mit anderen Worten, Sie können untere Grenzen pro Instanz berechnen. Der klassische Ansatz der CS-Theorie besteht darin, das Teilpackungsproblem zu lösen, das zur LP-Relaxation der Mengenabdeckung dual ist: Weisen Sie jedem abzudeckenden Element nichtnegative Kosten zu, so dass für jede Menge die Summe der Kosten der Elemente in dieser Menge ist höchstens die Kosten für das Set. Das Ziel besteht darin, die Summe über jedes Element der Elementkosten zu maximieren.

Es gibt sogar stärkere Erleichterungen, die den Rechenaufwand für die Qualität beeinträchtigen (z. B. anstatt Kosten einzelnen Elementen zuzuweisen, Kosten Teilmengen von k Elementen zuzuweisen).