Max-Cut mit negativen Gewichtsrändern

35

Sei ein Graph mit der Gewichtsfunktion . Das Max-Cut-Problem besteht darin, zu finden: If Die Gewichtsfunktion ist nicht negativ (dhG = ( V , E , W ) w : E R arg max S V Σ ( u , v ) E : u S , v S w ( u , v ) , w ( e ) 0G=(V,E,w)w:ER

argmaxSV(u,v)E:uS,vSw(u,v)
w(e)0 für alle e EeE ), dann gibt es viele extrem einfache 2-Approximationen für max-cut. Zum Beispiel können wir:
  1. Wähle eine zufällige Untergruppe von Vertices SS .
  2. Wählen Sie eine Reihenfolge für die Eckpunkte und platzieren Sie gierig jeden Eckpunkt vv in SS oder ˉSS¯ , um die bisher ausgeschnittenen Kanten zu maximieren
  3. Lokale Verbesserungen vornehmen : Wenn es in S einen Scheitelpunkt SSgibt, der nach \ bar {S} verschoben werden kann ˉSS¯, um den Schnitt zu erhöhen (oder umgekehrt), führen Sie den Schritt aus.

Die Standardanalyse all dieser Algorithmen zeigt tatsächlich, dass der resultierende Schnitt mindestens so groß ist wie 12eEw(e)12eEw(e) , was eine Obergrenze von 1/21/2 das gewicht des max-cut wenn ww nicht negativ ist - aber wenn einige kanten ein negatives gewicht haben dürfen, ist es nicht!

Zum Beispiel kann Algorithmus 1 (Auswahl einer zufälligen Untergruppe von Eckpunkten) bei Diagrammen mit negativer Kantengewichtung eindeutig versagen.

Meine Frage ist:

Gibt es einen einfachen kombinatorischen Algorithmus, der eine O (1) -Näherung an das Max-Cut-Problem in Graphen mit negativen Kantengewichten liefert?

Um das möglicherweise klebrige Problem der Max-Cut-Annahme mit dem Wert 0 zu vermeiden 00, werde ich zulassen, dass e E w ( e ) > 0eEw(e)>0 , und / oder mit Algorithmen zufrieden sein, die zusätzlich zu einem kleinen additiven Fehler führen eine multiplikative Faktorapproximation.

Aaron Roth
quelle
1
Ist die Bedingung "einfach kombinatorisch" hier wesentlich?
Hsien-Chih Chang 張顯 張顯 20.10.10
Am meisten interessiert mich ein einfacher, kombinatorischer Algorithmus wie die 2-Approximationen für den positiven Gewichtsfall. Beachten Sie, dass ich nach einer O (1) -Näherung frage. Daher würde ich erwarten, dass dies mit einem einfachen Algorithmus möglich sein sollte, wenn dies mit einem beliebigen Algorithmus erreicht werden kann. Es würde mich aber auch interessieren, welche Leistungsgarantien für SDP-Algorithmen auf Graphen mit negativer Kantengewichtung bestehen oder ob es keinen Algorithmus zur Approximation konstanter Faktoren gibt, wenn . P N PPNP
Aaron Roth

Antworten:

28

Hier war mein erster Versuch einer Auseinandersetzung. Es war falsch, aber ich habe es nach dem "EDIT:" behoben

Wenn Sie das Max-Cut-Problem mit negativen Kantengewichten effizient näherungsweise lösen könnten, könnten Sie das Max-Cut-Problem nicht mit positiven Kantengewichten lösen? Beginnen Sie mit einem Max-Cut-Problem, dessen optimale Lösung b ist . Setzen Sie nun eine große negative Gewichtungskante (mit Gewicht - a ) zwischen u und v . Die optimale Lösung für das neue Problem ist b - a , daher erhalten Sie mit unserem hypothetischen Approximationsalgorithmus eine Lösung mit maximalem Schnitt, deren Wert höchstens ( b - a ) / 2 schlechter als optimal ist. In der Originalgrafik ist der maximale Schnitt noch maximalbauvba(ba)/2( b - a ) / 2 schlechter als optimal. Wenn Sie a in der Nähe von b wählen, verletzt dies das Unannäherungsergebnis, dass Sie, wenn P NP,den Maximalschnittnicht besser als einen 16 / 17- Faktorapproximieren können. (ba)/2ab16/17

BEARBEITEN:

Der obige Algorithmus funktioniert nicht, da Sie nicht garantieren können, dass sich u und v auf entgegengesetzten Seiten des Schnitts im neuen Diagramm befinden, selbst wenn sie ursprünglich waren. Ich kann dies jedoch wie folgt beheben.uv

Nehmen wir an, wir haben einen Approximationsalgorithmus, der einen Schnitt innerhalb eines Faktors von 2 von OPT ergibt, solange die Summe aller Kantengewichte positiv ist.

Beginnen Sie wie oben mit einem Diagramm G mit allen nicht negativen Gewichten an den Kanten. Wir werden eine modifizierte Graph finden G * mit einigen negativen Gewichten , so dass , wenn wir den max Schnitt annähern können G * innerhalb eines Faktors von 2, wir den max Schnitt annähern können GGGGG sehr gut.

Wählen Sie zwei Scheitelpunkte u und v und hoffen Sie, dass sie sich auf den gegenüberliegenden Seiten des maximalen Schnitts befinden. (Sie können dies für alle möglichen v wiederholen, um sicherzustellen, dass ein Versuch funktioniert.) Setzen Sie nun ein großes negatives Gewicht - d auf alle Kanten ( u , x ) und ( v , x ) für x u , v und ein großes positives Gewicht a auf Kante ( u , v ) . Es sei angenommen , dass der optimale Schnitt Gewicht aufweist O P T .uvvd(u,x)(v,x)xu,va(u,v)OPT

Ein Schnitt mit dem Wert c in G , bei dem sich die Scheitelpunkte u und v auf derselben Seite des Schnitts befinden, hat jetzt den Wert c - 2 d m, wobei m die Anzahl der Scheitelpunkte auf der anderen Seite des Schnitts ist. Ein Schnitt mit ( u , v ) auf gegenüberliegenden Seiten mit dem ursprünglichen Wert c hat jetzt den Wert c + a - ( n - 2 ) d . Wenn wir also d groß genug wählen , können wir alle Schnitte mit u und erzwingencGuvc2dmm(u,v)cc+a(n2)ddu vvauf der gleichen Seite negativen Wert zu haben, so dass , wenn es ein Schnitt mit positivem Wert ist, dann ist die optimale cut in G * haben u und v auf gegenüberliegenden Seiten. Beachten Sie, dass wir jedem Schnitt mit u und v ein festes Gewicht ( a - ( n - 2 ) d ) hinzufügenGuv(a(n2)d)uv auf gegenüberliegenden Seiten .

Sei f = ( a - ( n - 2 ) d ) . Wählen Sie a so, dass f - 0.98 O P T (wir werden dies später begründen). Ein Schnitt mit dem Gewicht c in G mit u und v auf gegenüberliegenden Seiten wird nun ein Schnitt mit dem Gewicht c - 0,98 O P T . Dies bedeutet, dass der optimale Schnitt in G ein Gewicht von 0,02 O P hat . Unser neuer Algorithmus findet einen Einschnittf=(a(n2)d)af0.98OPTcGuvc0.98OPTG T hat0.02OPTG * mit Gewicht mindestens 0,01 O P T . Dies führt zu einem Schnitt in der Originalkurve G mit einem Gewicht von mindestens 0,99 O P T (da alle Schnitte in G mit positivem Gewicht u und v trennenG0.01OPTG0.99OPTGuv ), der besser ist als das Ergebnis der Unangemessenheit.

Es ist kein Problem, d groß genug zu wählen , um einen Schnitt mit u und v auf derselben Seite negativ zu machen, da wir d so groß wählen können, wie wir wollen. Aber wie haben wir a so gewählt, dass f - .99 O P T, als wir O P T nicht kannten ? Wir können O P T sehr gut approximieren ... wenn T die Summe der Kantengewichte in G ist , wissen wir 1duvdaf.99OPTOPTOPTTG2 TOPTT. So haben wir einen ziemlich engen Bereich von Werten fürf, und wir können iterierenfzwischenEinnahme aller Werte-0,49Tund-.99Tin Intervallen von0,005T. Für eines dieser Intervalle istf-0,98OPTgarantiert, und daher wird garantiert, dass eine dieser Iterationen einen guten Schnitt zurückgibt.12TOPTTff.49T.99T0.005Tf0.98OPT

Schließlich müssen wir überprüfen, ob das neue Diagramm Kantengewichte aufweist, deren Summe positiv ist. Wir begannen mit einem Diagramm, dessen Kantengewichte die Summe T hatten , und addierten f zur Summe der Kantengewichte. Da - 0,99 T f - 0,49 T , sind wir in Ordnung Tf.99Tf.49T

Peter Shor
quelle
1
Aber was sind deine u und v ? Die übliche Formulierung des Max-Cut-Problems enthält keine "speziellen Knoten", die getrennt werden müssen. uv
Jukka Suomela
3
Hallo Ian - ich denke nicht, dass das funktioniert. Warum müssen u und v , die im Originalgraphen durch den Max-Cut getrennt sind, notwendigerweise vorhanden sein und durch den Max-Cut getrennt bleiben, nachdem eine starke negative Flanke zwischen ihnen hinzugefügt wurde? Betrachten Sie zum Beispiel das gesamte Diagramm - das Hinzufügen einer einzelnen, willkürlich negativen Flanke an einer beliebigen Stelle ändert den Schnittwert überhaupt nicht. uv
Aaron Roth
2
Ein Problem besteht darin, dass Sie den Wert verschiedener Schnitte um unterschiedliche Beträge ändern, wenn Sie eine negative Kante zwischen jedem Scheitelpunktpaar hinzufügen. (Wir subtrahieren zum Beispiel | S || ˉ S |a vom Wert von Schnitt S ). Wir haben also das Problem, dass die Identität des Maximalschnitts im modifizierten Diagramm nicht unbedingt dem Maximalschnitt im Originaldiagramm entspricht. |S||S¯|aS
Aaron Roth
1
@Peter: In the paragraph after the one I quoted you choose aa sufficiently small to make f0.98OPTf0.98OPT. You can't safely choose aa to be sufficiently large in one paragraph and sufficiently small in the next! In particular, there is no way to choose aa and dd to ensure that c+a(n2)d>cdmc+a(n2)d>cdm for all 0mn0mn and simultaneously have a(n2)d=f0.98OPTa(n2)d=f0.98OPT. This follows because c+a(n2)d>cdmc+a(n2)d>cdm for all 0mn0mn implies that f=a(n2)d>0f=a(n2)d>0.
Warren Schudy
2
@Warren, You choose dd large enough so that cdm<0cdm<0 for all cuts. This can be done by choosing dd sufficiently large. You then choose aa the right size so that the optimal cut is just barely above 00. Read the last two paragraphs of my answer.
Peter Shor
11

In the article "Approximate Max Cut" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

Approximating the cut-norm via grothendieck’s inequality, Noga Alon and Assaf Naor, SIAM Journal on Computing, 2006.

It is indeed an SDP algorithm, and it seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!

Hsien-Chih Chang 張顯之
quelle
the problem in Alon-Naor is similar but I don't think there is a ratio preserving reduction. their problem is to maximize xTMyxTMy where x,y{±1}nx,y{±1}n and MM is an n×nn×n matrix. for max-cut and its close relatives it's crucial that x=yx=y
Sasho Nikolov
@SashoNikolov: for the cut norm it's immaterial, up to constant factors, whether we demand x=yx=y or not.
david
@david I know this reduction, but the statement that's actually true is that maxx|xTMx|maxx,yxTMy4maxx|xTMx|maxx|xTMx|maxx,yxTMy4maxx|xTMx| where all maximums are over {1,1}n{1,1}n, and MM is symmetric with nonnegative diagonal. However, the problem maxx|xTMx|maxx|xTMx| can have very different value from maxxxTMxmaxxxTMx (which is what we need for MaxCut). For example, consider M=IJM=IJ, where JJ is the n×nn×n all ones matrix. You can see maxxxTMxmaxxxTMx is about n/2n/2, while maxx|xTMx|maxx|xTMx| is n2nn2n.
Sasho Nikolov
6

Your problem has a logarithmic approximation by reduction to a quadratic programming problem.

The MaxQP problem is the problem of approximating the quadratic form xTMxxTMx for a n×nn×n matrix MM, where xx ranges over {±1}n{±1}n. MaxCut can be written in this form by setting M=12n(we)I12AM=12n(we)I12A where II is the identity matrix and AA is the adjacency matrix. The MaxQP algorithm of Charikar and Wirth gives an O(logn)O(logn) approximation for MaxQP as long as MM has a non-negative diagonal. So as long as we0we0, MaxCut with negative weights has a logarithmic approximation.

Sasho Nikolov
quelle