Approximationshärte - additiver Fehler

Es gibt eine reiche Literatur und mindestens ein sehr gutes Buch, in dem die bekannte Härte von Näherungsergebnissen für NP-harte Probleme im Zusammenhang mit multiplikativen Fehlern dargelegt ist (z. B. ist die 2-Näherung für die Vertex-Abdeckung unter der Annahme von UGC optimal). Dies schließt auch gut verstandene Näherungskomplexitätsklassen wie APX, PTAS usw. ein.

Was ist bekannt, wenn additive Fehler berücksichtigt werden sollen? Eine Literaturrecherche zeigt einige Ergebnisse für die obere Schranke, insbesondere für das Verpacken von Behältern (siehe z. B. http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), ist jedoch vorhanden eine umfassendere Klassifizierung der Komplexitätsklassen oder gibt es einen Grund, warum sie nicht so interessant oder relevant ist?

Als weiteren Kommentar, zum Beispiel für das Verpacken von Behältern, gibt es meines Wissens keinen theoretischen Grund, warum ein Poly-Zeit-Algorithmus, der immer in einem additiven Abstand vom Optimum von 1 liegt, nicht gefunden werden konnte (obwohl ich korrigiert werden muss) ). Würde ein solcher Algorithmus irgendwelche Komplexitätsklassen kollabieren lassen oder irgendeine andere signifikante theoretische Auswirkung haben?

EDIT: Der Schlüsselbegriff, den ich nicht verwendet habe, ist "asymptotische Approximationsklasse" (danke Oleksandr). Es scheint, dass es in diesem Bereich einige Arbeiten gibt, aber es hat noch nicht den gleichen Reifegrad wie die Theorie der klassischen Approximationsklassen erreicht.

Die Frage ist etwas offen, daher glaube ich nicht, dass sie vollständig beantwortet werden kann. Dies ist eine teilweise Antwort.

Eine einfache Beobachtung ist, dass viele Probleme uninteressant sind, wenn wir die additive Approximation betrachten. Beispielsweise ist die objektive Funktion des Max-3SAT-Problems traditionell die Anzahl der erfüllten Klauseln. In dieser Formulierung entspricht die Approximation von Max-3SAT innerhalb eines additiven O (1) -Fehlers der exakten Lösung von Max-3SAT, da die Zielfunktion durch mehrfaches Kopieren der Eingangsformel skaliert werden kann. Die multiplikative Approximation ist für die Probleme dieser Art wesentlich wichtiger.

[Bearbeiten: In der vorherigen Überarbeitung hatte ich Independent Set als Beispiel im vorherigen Absatz verwendet, aber ich habe es in Max-3SAT geändert, da Independent Set kein gutes Beispiel ist, um den Unterschied zwischen multiplikativer Approximation und additiver Approximation zu veranschaulichen. Die Approximation der unabhängigen Menge selbst innerhalb eines multiplikativen Faktors O (1) ist ebenfalls NP-hart. Tatsächlich zeigt Håstad [Has99] eine viel stärkere Unangemessenheit für Independent Set.

Aber wie Sie sagten, ist die additive Approximation interessant für die Probleme wie das Packen von Behältern, bei denen wir die Zielfunktion nicht skalieren können. Darüber hinaus können wir ein Problem oft umformulieren, so dass eine additive Approximation interessant wird.

Wenn zum Beispiel die Zielfunktion von Max-3SAT als das Verhältnis der Anzahl erfüllter Klauseln zur Gesamtzahl der Klauseln neu definiert wird (wie dies manchmal der Fall ist), wird die additive Approximation interessant. In dieser Einstellung ist die additive Approximation nicht schwerer als die multiplikative Approximation in dem Sinne, dass die Approximierbarkeit innerhalb eines multiplikativen Faktors 1 - ε (0 < ε <1) die Approximierbarkeit innerhalb eines additiven Fehlers ε impliziert , da der optimale Wert immer höchstens 1 ist.

Eine interessante Tatsache (die leider oft zu sein scheint übersehen) ist , dass viele Nichtapproximierbarkeitsresultate die NP-Vollständigkeit bestimmter beweisen Lücke Problemewas sich nicht aus der bloßen NP-Härte der multiplikativen Approximation ergibt (siehe auch Petrank [Pet94] und Goldreich [Gol05, Abschnitt 3]). In Anlehnung an Max-3SAT ist es ein bekanntes Ergebnis von Håstad [Has01], dass es NP-schwer ist, Max-3SAT mit einem konstanten Multiplikationsfaktor besser als 7/8 anzunähern. Dieses Ergebnis allein scheint nicht zu bedeuten, dass es NP-schwer ist, die Verhältnisversion von Max-3SAT innerhalb eines konstanten additiven Fehlers über einen bestimmten Schwellenwert hinaus anzunähern. Was Håstad [Has01] jedoch beweist, ist stärker als die rein multiplikative Unangemessenheit: Er beweist, dass das folgende Versprechungsproblem für jede Konstante 7/8 < s <1 NP-vollständig ist :

Gap-3SAT _s
Instanz : Ein CNF Formel φ , wobei jede Klausel enthält genau drei verschiedene Variablen.
Ja-Versprechen : φ ist erfüllbar.
No-Versprechen : Keine Wahrheit Zuordnung erfüllt mehr als s Anteil der Klauseln von φ.

Daraus können wir schließen, dass es NP-schwer ist, die Verhältnisversion von Max-3SAT innerhalb eines additiven Fehlers besser als 1/8 anzunähern. Andererseits gibt die übliche einfache Zufallszuordnung eine Annäherung innerhalb eines additiven Fehlers von 1/8. Daher ergibt das Ergebnis von Håstad [Has01] nicht nur die optimale multiplikative Unangemessenheit für dieses Problem, sondern auch die optimale additive Unangemessenheit. Ich vermute, dass es viele solche additiven Unannäherungsergebnisse gibt, die in der Literatur nicht explizit auftauchen.

Verweise

[Gol05] Oded Goldreich. Auf Versprechen Probleme (eine Umfrage in Erinnerung an Shimon Even [1935-2004]). Elektronisches Kolloquium zur rechnergestützten Komplexität , Bericht TR05-018, Februar 2005. http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad. Clique ist innerhalb von n ^{1 - ε} schwer zu approximieren . Acta Mathematica , 182 (1): 105–142, März 1999. http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad. Einige optimale Unannäherungsergebnisse. Journal of the ACM , 48 (4): 798–859, Juli 2001. http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank. Die Härte der Approximation: Lückenortung. Computational Complexity , 4 (2): 133–157, April 1994. http://dx.doi.org/10.1007/BF01202286

Dies ist eine teilweise Antwort

$ABS$$ABS$

$NP$

-Jede kubische Grafik ist in der Polynomzeit mit Kante 4 färbbar, aber die Färbung mit Kante 3 ist NP-hart.

$ABS$$P=NP$

Es gibt eine aktuelle Arbeit über asymptotische Approximationsklassen und deren Vergleich mit klassischen Gegenstücken.

Erik Jan van Leeuwen und Jan van Leeuwen. Struktur der Polynom-Zeit-Approximation . Technischer Bericht UU-CS-2009-034. Dezember 2009.