Max-Cut mit negativen Gewichtsrändern

Sei ein Graph mit der Gewichtsfunktion . Das Max-Cut-Problem besteht darin, zu finden: If Die Gewichtsfunktion ist nicht negativ (dh $G = (V, E, w)$ $w:E\rightarrow \mathbb{R}$

arg max S \subset V \sum (u, v) \in E : u \in S, v \notin S w (u, v)

$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$

w(e)≥0 $w(e) \geq 0$ für alle

e∈E $e \in E$ ), dann gibt es viele extrem einfache 2-Approximationen für max-cut. Zum Beispiel können wir:

Wähle eine zufällige Untergruppe von Vertices $S$ .
Wählen Sie eine Reihenfolge für die Eckpunkte und platzieren Sie gierig jeden Eckpunkt $v$ in $S$ oder $\bar{S}$ , um die bisher ausgeschnittenen Kanten zu maximieren
Lokale Verbesserungen vornehmen : Wenn es in einen Scheitelpunkt $S$ gibt, der nach verschoben werden kann $\bar{S}$ , 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 $\frac{1}{2}\sum_{e \in E}w(e)$ , was eine Obergrenze von $1/2$ das gewicht des max-cut wenn $w$ 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 zu vermeiden $0$ , werde ich zulassen, dass $\sum_{e \in E}w(e) > 0$ , und / oder mit Algorithmen zufrieden sein, die zusätzlich zu einem kleinen additiven Fehler führen eine multiplikative Faktorapproximation.

ds.algorithms graph-theory approximation-algorithms max-cut Aaron Roth
quelle

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≠NP $P \ne NP$

Aaron Roth

Antworten:

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 . Setzen Sie nun eine große negative Gewichtungskante (mit Gewicht ) zwischen und . Die optimale Lösung für das neue Problem ist , daher erhalten Sie mit unserem hypothetischen Approximationsalgorithmus eine Lösung mit maximalem Schnitt, deren Wert höchstens schlechter als optimal ist. In der Originalgrafik ist der maximale Schnitt noch maximal $b$ $-a$ $u$ $v$ $b-a$ $(b-a)/2$ schlechter als optimal. Wenn Sie Nähe von wählen, verletzt dies das Unannäherungsergebnis, dass Sie, wenn P NP,den Maximalschnittnicht besser als einen Faktorapproximieren können. $(b-a)/2$ $a$ $b$ $\neq$ $16/17$

BEARBEITEN:

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

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 mit allen nicht negativen Gewichten an den Kanten. Wir werden eine modifizierte Graph finden mit einigen negativen Gewichten , so dass , wenn wir den max Schnitt annähern können innerhalb eines Faktors von 2, wir den max Schnitt annähern können $G$ $G^*$ $G^*$ $G$ sehr gut.

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

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

Sei . Wählen Sie so, dass (wir werden dies später begründen). Ein Schnitt mit dem Gewicht in mit und auf gegenüberliegenden Seiten wird nun ein Schnitt mit dem Gewicht . Dies bedeutet, dass der optimale Schnitt in ein Gewicht von . Unser neuer Algorithmus findet einen Einschnitt $f=(a - (n-2)d)$ $a$ $f \approx - 0.98 OPT$ $c$ $G$ $u$ $v$ $c - 0.98 OPT$ $G^*$ $0.02 OPT$ mit Gewicht mindestens . Dies führt zu einem Schnitt in der Originalkurve mit einem Gewicht von mindestens (da alle Schnitte in mit positivem Gewicht und trennen $G^*$ $0.01 OPT$ $G$ $0.99OPT$ $G^*$ $u$ $v$ ), der besser ist als das Ergebnis der Unangemessenheit.

Es ist kein Problem, groß genug zu wählen , um einen Schnitt mit und auf derselben Seite negativ zu machen, da wir so groß wählen können, wie wir wollen. Aber wie haben wir so gewählt, dass als wir nicht kannten ? Wir können sehr gut approximieren ... wenn die Summe der Kantengewichte in , wissen wir $d$ $u$ $v$ $d$ $a$ $f \approx -.99OPT$ $OPT$ $OPT$ $T$ $G$ . So haben wir einen ziemlich engen Bereich von Werten für, und wir können iterierenzwischenEinnahme aller Werteundin Intervallen von. Für eines dieser Intervalle istgarantiert, und daher wird garantiert, dass eine dieser Iterationen einen guten Schnitt zurückgibt. $\frac{1}{2}T \leq OPT \leq T$ $f$ $f$ $-.49T$ $-.99T$ $0.005T$ $f \approx -0.98 OPT$

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 , und addierten zur Summe der Kantengewichte. Da , sind wir in Ordnung $T$ $f$ $-.99T \leq f \leq -.49T$

Peter Shor
quelle

Aber was sind deine

und

? Die übliche Formulierung des Max-Cut-Problems enthält keine "speziellen Knoten", die getrennt werden müssen. u $u$

v $v$

Jukka Suomela

Hallo Ian - ich denke nicht, dass das funktioniert. Warum müssen

und

, 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. u $u$

v $v$

Aaron Roth

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

vom Wert von Schnitt

). Wir haben also das Problem, dass die Identität des Maximalschnitts im modifizierten Diagramm nicht unbedingt dem Maximalschnitt im Originaldiagramm entspricht. |S|⋅|S¯|⋅a $|S|\cdot|\bar{S}|\cdot a$

S $S$

Aaron Roth

@Peter: In the paragraph after the one I quoted you choose

a $a$ sufficiently small to make

f≈−0.98OPT $f \approx -0.98 OPT$ . You can't safely choose

a $a$ to be sufficiently large in one paragraph and sufficiently small in the next! In particular, there is no way to choose

a $a$ and

d $d$ to ensure that

c+a−(n−2)d>c−dm $c+a-(n-2)d>c-dm$ for all

0≤m≤n $0\le m \le n$ and simultaneously have

a−(n−2)d=f≈−0.98⋅OPT $a-(n-2)d = f\approx -0.98 \cdot OPT$ . This follows because

c+a−(n−2)d>c−dm $c+a-(n-2)d>c-dm$ for all

0≤m≤n $0\le m \le n$ implies that

f=a−(n−2)d>0 $f=a-(n-2)d > 0$ .

Warren Schudy

@Warren, You choose

d $d$ large enough so that

c−dm<0 $c-dm<0$ for all cuts. This can be done by choosing

d $d$ sufficiently large. You then choose

a $a$ the right size so that the optimal cut is just barely above

0 $0$ . Read the last two paragraphs of my answer.

Peter Shor

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

xTMy $x^TMy$ where

x,y∈{±1}n $x, y \in \{\pm 1\}^n$ and

M $M$ is an

n×n $n \times n$ matrix. for max-cut and its close relatives it's crucial that

x=y $x = y$

Sasho Nikolov

@SashoNikolov: for the cut norm it's immaterial, up to constant factors, whether we demand

x=y $x=y$ or not.

david

@david I know this reduction, but the statement that's actually true is that

maxx|xTMx|≤maxx,yxTMy≤4maxx|xTMx| $\max_x |x^TMx| \leq \max_{x, y}{x^TMy} \leq 4 \max_x |x^TMx|$ where all maximums are over

{−1,1}n $\{-1, 1\}^n$ , and

M $M$ is symmetric with nonnegative diagonal. However, the problem

maxx|xTMx| $\max_x |x^TMx|$ can have very different value from

maxxxTMx $\max_x x^TMx$ (which is what we need for MaxCut). For example, consider

M=I−J $M = I-J$ , where

J $J$ is the

n×n $n\times n$ all ones matrix. You can see

maxxxTMx $\max_{x}{x^TMx}$ is about

n/2 $n/2$ , while

maxx|xTMx| $\max_{x}{|x^TMx|}$ is

n2−n $n^2 - n$ .

Sasho Nikolov

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

The MaxQP problem is the problem of approximating the quadratic form $x^TMx$ for a $n \times n$ matrix $M$ , where $x$ ranges over $\{\pm 1\}^n$ . MaxCut can be written in this form by setting $M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$ where $I$ is the identity matrix and $A$ is the adjacency matrix. The MaxQP algorithm of Charikar and Wirth gives an $O(\log n)$ approximation for MaxQP as long as $M$ has a non-negative diagonal. So as long as $\sum{w_e} \geq 0$ , MaxCut with negative weights has a logarithmic approximation.

Sasho Nikolov
quelle