Ist die MAX CUT-Approximation beständig?

8

Das CSP-Optimierungsproblem ist approximationsresistent, wenn es schwer ist, den Approximationsfaktor einer zufälligen Zuordnung zu übertreffen. Zum Beispiel ist MAX 3-LIN approximationsbeständig, da eine zufällige Zuordnung einen Bruchteil der linearen Gleichungen erfüllt, das Erreichen des Approximationsfaktors jedoch hart ist.1 / 2 1 / 2 + ε N PNP1/21/2+ϵNP

MAX CUT ist ein grundlegendes vollständig. Es kann als CSP-Problem der Lösung der linearen Gleichungen Modulo 2 ( mod 2) formuliert werden . Eine zufällige Zuordnung erreicht einen -Näherungsfaktor (der Gesamtzahl der Kanten ). Haglin und Venkatesan bewiesen , dass eine Annäherung Faktor zu erreichen ist -hard (dh der Suche nach einem Schnitt besser als ). Hastad zeigte jedoch, dass MAX CUT innerhalb des optimalen Schnitts nicht annähernd 16/17 Faktor ist, es sei denn,x i + x j = 1 1 / 2 | E | 1 / 2 + ε N P | E | / 2 16 / 17 + ε P = N P | E |NPxi+xj=11/2|E|1/2+ϵNP|E|/216/17+ϵP=NP. Goemans und Williamson gaben einen SDP-basierten Polynomzeitalgorithmus mit einem Approximationsfaktor von 0,878 (innerhalb des optimalen Schnitts) an, der unter der Annahme der Unique Games Conjecture optimal ist. Es scheint mir, dass das Ausdrücken des Approximationsfaktors relativ zur Gesamtzahl der Einschränkungen ( ) natürlicher ist und mit der für das MAX 3-LIN-Problem verwendeten Konvention übereinstimmt.|E|

Warum wird der Approximationsfaktor für MAX CUT relativ zur Größe des optimalen Schnitts anstelle der Anzahl der Einschränkungen (Anzahl der Kanten) angegeben? Bin ich zu Recht zu dem Schluss gekommen, dass MAX CUT approximationsbeständig ist, wenn der Approximationsfaktor relativ zur Gesamtzahl der Einschränkungen ( ) ist?|E|

Mohammad Al-Turkistany
quelle
Ich frage mich auch, ob Hastads Max 3-LIN-Version des PCP-Theorems (direkt oder indirekt) aus Haglin und Venkatesans In-Approximability-Ergebnis von MAX CUT abgeleitet werden kann.
Mohammad Al-Turkistany

Antworten:

13

Wenn Sie die Approximation als Verhältnis zwischen der Anzahl der von Ihrem Algorithmus erfüllten Einschränkungen und der Gesamtzahl der Einschränkungen messen, sind trivialerweise alle Probleme mit der Erfüllung von Einschränkungen unbedingt approximationsresistent.

Per Definition ist ein Problem approximationsresistent, wenn das (Worst-Case-) Approximationsverhältnis einer Zufallslösung (bis zu einem additiven -Term) unter den (Worst-Case-) Approximationsverhältnissen, die von allen Polynomialzeitalgorithmen erreicht werden, am besten möglich ist .o(1)

Mit Ihrer Definition des Approximationsverhältnisses erhalten Sie einen Approximationswiderstand von Max Cut (und alle Probleme mit der Einschränkungszufriedenheit), nur weil Sie immer Instanzen konstruieren können, für die das Verhältnis (im Durchschnitt) durch eine zufällige Zuweisung mehr oder weniger (bis zu einem ) beträgt Begriff) das gleiche wie das Verhältnis, das durch eine optimale Zuordnung gegeben ist.o(1)

Im Max-Cut-Problem ist eine Clique auf Eckpunkten beispielsweise ein Diagramm mit Kanten, in dem ein optimaler Schnitt 2/4 schneidet Kanten. Dies bedeutet , dass jeder Algorithmus, und insbesondere hat jeden Polynomialzeitalgorithmus, ein Worst-Case - Approximation Verhältnis (entsprechend Ihre Definition) , die höchstens auf -eckiges Graphen. Die Zufallszuweisung hat in allen Instanzen das Verhältnis , und daher kann kein Algorithmus besser als der Zufallsalgorithmus sein, und das Problem ist approximationsresistent.nn 2 / 4 1 / 2 + O ( 1 / n ) n 1 / 2(n2)=n(n1)/2n2/41/2+O(1/n)n1/2

Luca Trevisan
quelle
Danke Luca für deine nette Antwort. Mir ist nicht klar, warum der Approximationsfaktor von MAX 3-LIN (mod 2) relativ zur Gesamtzahl der Randbedingungen (Anzahl der linearen Gleichungen) anstelle des Optimums angegeben wird.
Mohammad Al-Turkistany
3
Die negativen Ergebnisse sind nicht: Hastads Ergebnis der Approximationshärte ist, dass es für jedes NP-schwierig ist, Lösungen zu finden, die mehr als einen Bruchteil der durch ein {\ erfüllten Gleichungen erfüllen em optimale} Lösung. (Es wäre trivial zu sagen, dass es keinen Algorithmus gibt, der immer mindestens einen Bruchteil der Einschränkungen erfüllt. Denken Sie an die Instanz ). 1ϵ>0112+ϵxyz=0; xyz=112+ϵxyz=0;xyz=1
Luca Trevisan