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

16

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:supAOPTMINAAOPTinfΩAΩOPTΩ

  • 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.Ω22

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?

Oleksandr Bondarenko
quelle
2
Ich habe diesen Begriff noch nie gesehen und finde ihn zumindest interessant. Sehr neugierig auf die Antworten! (obwohl der wahre Grund so trivial sein kann wie "Doh, habe nie darüber nachgedacht" oder "Beweise werden schwieriger" oder "Kann es nicht mit anderen Ergebnissen vergleichen, wenn ich anfange")
Raphael

Antworten:

3

Es gibt zwei Interpretationen der Behauptung "Algorithmus findet eine Approximation von Problem "EINα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.EIN

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.CichCCich

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?)

Jukka Suomela
quelle
Ich verstehe deinen Standpunkt im zweiten Teil nicht. Jede überapproximierende Auswahl von Scheitelpunkten ist eine mögliche Scheitelpunktabdeckung. Wir müssen nicht wissen, dass der Algorithmus eine 2-Approximation dafür ist. Auf der anderen Seite könnte sogar eine 2-Approximation für eine unabhängige Menge sehr wohl eine nicht durchführbare Lösung ergeben. Es scheint also, dass die Gefahr der Unmöglichkeit mit dem Problem verbunden ist, nicht mit (nicht) bekannten Annäherungsgrenzen.
Raphael
@Raphael: Eine 2-Approximation der maximalen unabhängigen Menge ist per Definition eine unabhängige Menge (und ziemlich groß; sicherlich keine leere Menge).
Jukka Suomela
Macht nichts, lies zu schnell. Trotzdem sollte Ihr Punkt lauten: Ein Algorithmus ohne Annäherungsgarantie erledigt die Arbeit im Falle von VC, aber nicht im IS. (Sie vergleichen dort Äpfel und Birnen, nicht wahr?) Aber in welcher Beziehung steht diese Studie zur Wahl der Garantie? Beides würde genügen, um machbare Lösungen zu finden.
Raphael
@Raphael: Nein, ich sage , dass die triviale VC hat eine endliche Approximation Garantie (so etwas wie ), und es wird den Job zu erledigen, während die trivial ist nicht eine endliche Approximation Garantie hat, und es tut nicht erledige den Job. Daher sagen die Annäherungsgarantien zumindest etwas darüber aus, wie nützlich die Lösung ist. Ö(Δ)
Jukka Suomela
1
+1 weil Beispiele Spaß machen. Ich glaube nicht, dass es einen gut definierten Unterschied zwischen „das Problem ist einfach“ und „es gibt einen guten Algorithmus“ gibt, aber ich verstehe es irgendwie auf einer vagen Ebene.
Tsuyoshi Ito
3

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.

Tsuyoshi Ito
quelle
02ÖPTn/2
@Oleksandr: „Im Fall von Vertex Cover, obwohl die Approximation mit der schlechtesten Lösung übereinstimmt, wenn OPT⩾n / 2, haben wir Verhältnis 2.“ Ob Sie es als Nachteil betrachten oder nicht, ist ein Gesichtspunkt. Man kann argumentieren, dass es egal ist, welche Lösung ein Algorithmus erzeugt, wenn jede Lösung den Zielwert innerhalb eines Faktors von 2 hat. Das Standard-Approximationsverhältnis bildet die Situation wie folgt ab.
Tsuyoshi Ito
Wenn dieser Faktor 2 oder irgendein anderer kleiner Faktor die schlechteste Lösung ist, ist ein solches Ergebnis von geringem Nutzen.
Oleksandr Bondarenko
1
@Oleksandr: Wie gesagt, das ist eine Sichtweise.
Tsuyoshi Ito
3

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.

α=EINÖPT

α=Ω-EINΩ-ÖPTα100%

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

[Ω,ÖPT]

Raphael
quelle