Warum sind differentielle Approximationsverhältnisse trotz der behaupteten Vorteile im Vergleich zu Standardverhält- nissen nicht gut untersucht?

Es gibt eine Standard-Approximationstheorie, bei der das Approximationsverhältnis (für Probleme mit Objektiven) ist, - der von einigen Algorithmen und Wert - ein optimaler Wert. Und eine andere Theorie, die der Differentialapproximation, bei der das Approximationsverhältnis , - der schlechteste Wert einer realisierbaren Lösung für die gegebene Instanz. Die Autoren dieser Theorie behaupten, dass sie einige eindeutige Vorteile gegenüber der klassischen hat. Beispielsweise:$\sup\frac{A}{OPT}$$MIN$$A$$A$$OPT$$\inf\frac{\Omega-A}{\Omega-OPT}$$\Omega$

• es gibt das gleiche Näherungsverhältnis für solche Probleme wie Minimum Vertex Cover und Maximum Independent Set, von denen bekannt ist, dass sie nur unterschiedliche Realisierungen desselben Problems sind;
• Es gibt dasselbe Verhältnis für die Max- und Min-Versionen desselben Problems. Gleichzeitig wissen wir in der Standardtheorie, dass MIN TSP und MAX TSP sehr unterschiedliche Verhältnisse haben.
• Es misst die Entfernung nicht nur zum Optimum, sondern auch zum Pessimum . Im Fall von Vertex Cover besagt die Standard-Approximationstheorie, dass die beste obere Schranke ist. Wesentlich ist jedoch das maximale Verhältnis zwischen dem Pessimum und dem Optimum. Auf diese Weise wird garantiert, dass ein solcher Algorithmus die Lösung mit dem schlechtesten Wert ausgibt.$\Omega$$2$$2$

Mein Argument lautet: Bei der asymptotischen Analyse berücksichtigen wir keine Konstanten und Terme niedriger Ordnung (hier erinnere ich mich an das Zitat von Avi Widgerson: "Wir sind erfolgreich, weil wir die richtige Abstraktionsebene verwenden.") Abstraktionsgrad für den Vergleich der Ressourcennutzung des Algorithmus. Aber wenn wir die Approximation untersuchen, führen wir aus irgendeinem Grund den Unterschied an den Stellen ein, an denen wir ihn vermeiden können.

Meine Frage ist

warum die Differentialapproximationstheorie so schlecht studiert. Oder sind die Argumente nicht stark genug?

Es gibt zwei Interpretationen der Behauptung "Algorithmus findet eine Approximation von Problem "$A$$\alpha$$P$ :

1. Problem ist leicht zu lösen, da wir einen Algorithmus haben, der eine gute Näherung findet.$P$
2. Algorithmus ist gut , da er eine gute Annäherung findet.$A$

Ich denke, die klassische Definition des Approximationsfaktors betont die erste Interpretation. Wir klassifizieren Probleme danach, wie einfach sie sich relativ gut lösen lassen.

Das differentielle Approximationsverhältnis scheint der zweiten Interpretation etwas mehr Gewicht zu verleihen: Wir wollen keine trivialen Algorithmen "belohnen" (z. B. Algorithmen, die nur eine leere Menge oder die Menge aller Knoten ausgeben).

Natürlich sind beide gültige Standpunkte, aber sie sind unterschiedliche Standpunkte.

Wir können die Frage auch aus einer etwas praktischeren Perspektive untersuchen. Leider haben Vertex-Covers als solche nicht so viele direkte Verwendungen, aber lassen Sie uns aus Gründen der Argumentation diese beiden (etwas erfundenen) Anwendungen betrachten:

• Scheitelpunktabdeckung: Knoten sind Computer und Kanten sind Kommunikationsverbindungen. Wir möchten alle Kommunikationsverbindungen überwachen und daher muss mindestens ein Endpunkt jeder Kante einen speziellen Prozess ausführen.

• Unabhängige Menge: Knoten sind Worker und Kantenmodellkonflikte zwischen ihren Aktivitäten. Wir wollen eine Reihe von konfliktfreien Aktivitäten finden, die gleichzeitig ausgeführt werden können.

Jetzt haben beide Probleme eine triviale Lösung: Die Menge aller Knoten ist eine Scheitelpunktabdeckung, und die leere Menge ist eine unabhängige Menge.

Der Hauptunterschied besteht darin, dass mit dem Vertex-Cover-Problem die triviale Lösung die Aufgabe erledigt . Sicher, wir verbrauchen mehr Ressourcen als nötig, aber zumindest haben wir eine Lösung, die wir in der Praxis einsetzen können. Mit dem Independent-Set-Problem ist die triviale Lösung jedoch völlig nutzlos . Wir machen überhaupt keine Fortschritte. Niemand tut etwas. Die Aufgabe wird nie abgeschlossen.

In ähnlicher Weise können wir fast triviale Lösungen vergleichen: Scheitelpunktabdeckung , die aus den Endpunkten einer maximalen Übereinstimmung besteht, und unabhängige Menge , die das Komplement von . Auch hier erledigt die Aufgabe in unserer Anwendung, und diesmal verschwenden wir keine Ressourcen mehr als um den Faktor zwei. Aber könnte wieder eine leere Menge sein, die völlig nutzlos ist.$C$$I$$C$$C$$I$

Die Standarddefinition der Annäherungsgarantie sagt uns daher direkt, ob die Lösung nützlich ist oder nicht. Eine 2-Approximation der Scheitelpunktabdeckung erledigt die Aufgabe. Ein unabhängiger Satz ohne Annäherungsgarantie könnte völlig unbrauchbar sein.

In gewisser Weise versucht das Differential-Approximationsverhältnis zu messen, "wie nicht-trivial" die Lösung ist, aber spielt es in einer dieser Anwendungen eine Rolle? (Ist es in irgendeiner Anwendung wichtig?)

Ich kenne den Begriff der Differentialapproximation nicht und habe keine Theorie, warum er nicht gut erforscht ist. Ich möchte jedoch darauf hinweisen, dass es nicht immer wünschenswert ist, die Leistung eines Approximationsalgorithmus durch eine einzige Kennzahl zu beschreiben. In diesem Sinne fällt es mir schwer zuzustimmen, dass eine Maßnahme besser ist als eine andere.

Wie Sie bereits sagten, lässt die minimale Scheitelpunktabdeckung beispielsweise einen Algorithmus zur Polynomzeit-2-Approximation zu, während es NP-schwierig ist, die maximale unabhängige Menge auf ein konstantes Verhältnis zu approximieren. Obwohl ich verstehe, dass dies auf den ersten Blick überraschend sein kann, hat es eine legitime Bedeutung: (1) Die minimale Scheitelpunktabdeckung kann gut angenähert werden, wenn sie klein ist, aber (2) sie kann nicht gut angenähert werden, wenn sie groß ist. Wenn wir sagen, dass es NP-schwer ist, die minimale Scheitelpunktabdeckung (und die maximale unabhängige Menge) mit einem positiven konstanten Differentialnäherungsverhältnis zu approximieren, ignorieren wir die Eigenschaft (1) effektiv. Für einige Zwecke ist es wahrscheinlich gut genug, die Eigenschaft (1) zu ignorieren, aber dies ist sicherlich nicht immer der Fall.

Beachten Sie, dass wir das Approximationsverhältnis nicht immer verwenden, um die Leistung von Approximationsalgorithmen zu beschreiben. Um zum Beispiel ein auf dem PCP-Theorem basierendes Inapproximabilitätsergebnis in seiner vollen Allgemeinheit anzugeben, benötigen wir die Formulierung, die auf Lückenproblemen basiert. Siehe meine Antwort auf eine andere Frage für Details. In diesem Fall können wir weder unter Verwendung des Standardnäherungsverhältnisses noch unter Verwendung des Differentialnäherungsverhältnisses das Ergebnis in voller Allgemeinheit angeben.

Wie Tsuyoshi betont, könnte die Frage sein, für welche Art von Argument Sie die erhaltene Schranke verwenden möchten. Im Folgenden werde ich versuchen, zwei verschiedene Motivationen zu entwickeln.

$\alpha = \frac{A}{OPT}$

$\alpha = \frac{\Omega - A}{\Omega - OPT}$$\alpha\cdot 100\%$

Abhängig von der Art der Anweisung, die die abgeleitete Bindung unterstützen soll, sollten Sie die richtige Alternative auswählen.

$[\Omega, OPT]$