Max-cut z ujemnymi krawędziami wagi

$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$

e∈E $e \in E$

Odbiór losowego podzbioru wierzchołki . $S$
Wybierz kolejność na wierzchołkach i łapczywie umieść każdy wierzchołek w lub aby zmaksymalizować do tej pory przycięte krawędzie $v$ $S$ $\bar{S}$
Wprowadź lokalne ulepszenia: jeśli istnieje jakikolwiek wierzchołek w który można przenieść do celu zwiększenia cięcia (lub odwrotnie), wykonaj ruch. $S$ $\bar{S}$

Standardowa analiza wszystkich tych algorytmów pokazuje, że wynikowe cięcie jest co najmniej tak duże jak , co stanowi górną granicę na ciężar maksymalnego cięcia, jeśli nie jest ujemny - ale jeśli niektóre krawędzie mogą mieć ujemny ciężar, nie jest! $\frac{1}{2}\sum_{e \in E}w(e)$ $1/2$ $w$

Na przykład algorytm 1 (wybierz losowy podzbiór wierzchołków) może wyraźnie zawieść na wykresach z ujemnymi wagami krawędzi.

Moje pytanie brzmi:

Czy istnieje prosty algorytm kombinatoryczny, który otrzymuje przybliżenie O (1) do problemu maksymalnego cięcia na wykresach, które mogą mieć ujemne wagi krawędzi?

Aby uniknąć potencjalnie lepkiego problemu przy przyjmowaniu maksymalnej wartości , pozwolę, że , i / lub będę zadowolony z algorytmów, które powodują niewielki błąd addytywny oprócz przybliżenie współczynnika multiplikatywnego. $0$ $\sum_{e \in E}w(e) > 0$

— Aaron Roth
źródło

Czy warunek „prosty kombinatoryczny” jest tutaj niezbędny?

— Hsien-Chih Chang 張顯之

Najbardziej interesuje mnie prosty algorytm kombinatoryczny, taki jak 2-przybliżenia dla przypadku dodatniej wagi. Zauważ, że pytam o jakieś przybliżenie O (1), więc oczekiwałbym, że jeśli dowolny algorytm może to osiągnąć, powinno być to możliwe z prostym. Ale będzie również zainteresowany tym, co gwarancje wykonania są dla algorytmów SDP na wykresach z ujemnymi wagami krawędzi, albo dowód, że żaden algorytm przybliżenie stałym czynnikiem istnieje, jeżeli

. P≠NP $P \ne NP$

— Aaron Roth,

Odpowiedzi:

Oto moja pierwsza próba kłótni. To było złe, ale naprawiłem to po „EDYCJI:”

Jeśli potrafisz skutecznie w przybliżeniu rozwiązać problem maksymalnego cięcia przy ujemnych obciążeniach krawędzi, czy nie możesz go użyć do rozwiązania problemu maksymalnego cięcia przy dodatnich obciążeniach krawędzi? Zacznij od problemu maksymalnego cięcia, który chcesz rozwiązać, którego optymalnym rozwiązaniem jest . Teraz umieść dużą ujemną krawędź wagi (o wadze ) między i . Optymalnym rozwiązaniem nowego problemu jest , więc nasz hipotetyczny algorytm aproksymacyjny dostarczy Ci rozwiązanie z maksymalnym cięciem, którego wartość jest co najwyżej gorsza niż optymalna. Na oryginalnym wykresie maksymalne cięcie jest nadal co najwyżej $b$ $-a$ $u$ $v$ $b-a$ $(b-a)/2$ $(b-a)/2$ gorsze niż optymalne. Jeśli zdecydujesz blisko , ten jest niezgodny wynik inapproximability że jeśli P NP, nie można przybliżona maksymalna kroju lepiej niż czynnika. $a$ $b$ $\neq$ $16/17$

EDYTOWAĆ:

Powyższy algorytm nie działa, ponieważ nie można zagwarantować, że i znajdują się po przeciwnych stronach cięcia na nowym wykresie, nawet jeśli były pierwotnie. Mogę to jednak naprawić w następujący sposób. $u$ $v$

Załóżmy, że mamy algorytm aproksymacji, który da nam cięcie w granicach 2 OPT, o ile suma wszystkich wag krawędzi jest dodatnia.

Jak wyżej, zacznij od wykresu ze wszystkimi nieujemnymi wagami na krawędziach. Znajdziemy zmodyfikowany wykres z pewnymi ujemnymi wagami, tak że jeśli będziemy w stanie przybliżać maksymalne cięcie $G$ $G^*$ $G^*$ ze współczynnikiem 2, możemy bardzo dobrze przybliżać maksymalne cięcie $G$

Wybierz dwa wierzchołki i i miej nadzieję, że znajdują się one po przeciwnych stronach maksymalnego cięcia. (Możesz to powtórzyć dla wszystkich możliwych aby upewnić się, że jedna próba zadziała.) Teraz połóż dużą ujemną wagę na wszystkich krawędziach i dla i dużej dodatnia waga na krawędzi . Załóżmy, że optymalne cięcie ma ciężar . $u$ $v$ $v$ $-d$ $(u,x)$ $(v,x)$ $x \neq u,v$ $a$ $(u,v)$ $OPT$

Redukcja o wartości na , w którym wierzchołki i są po tej samej stronie cięcia, teraz wartości w , gdzie jest liczbą wierzchołków na drugiej stronie cięcia. Cięcie z po przeciwnych stronach o pierwotnej wartości ma teraz wartość . Zatem jeśli wybieramy wystarczająco duże, możemy wymusić wszystkie cięcia za pomocą i $c$ $G$ $u$ $v$ $c - 2dm$ $m$ $(u,v)$ $c$ $c + a - (n-2)d$ $d$ $u$ $v$ po tej samej stronie, aby mieć wartość ujemną, więc jeśli istnieje jakiekolwiek cięcie o wartości dodatniej, wówczas optymalne cięcie w będzie miało i po przeciwnych stronach. Zauważ, że dodajemy stały ciężar do każdego cięcia za pomocą i po przeciwnych stronach. $G^*$ $u$ $v$ $(a - (n-2)d)$ $u$ $v$

Niech . Wybierz tak, że (będziemy usprawiedliwiać tym później). Redukcja o masie na o i w przeciwnych stronach się teraz cięte z masy . Oznacza to, że optymalne cięcie w ma wagę $f=(a - (n-2)d)$ $a$ $f \approx - 0.98 OPT$ $c$ $G$ $u$ $v$ $c - 0.98 OPT$ $G^*$ $0.02 OPT$ . Nasz nowy algorytm znajduje cięcie w $G^*$ o masie co najmniej . Przekłada się to na cięcie na oryginalnym wykresie o wadze co najmniej (ponieważ wszystkie cięcia w o dodatniej wadze oddzielają i $0.01 OPT$ $G$ $0.99OPT$ $G^*$ $u$ ), co jest lepsze niż wynik niedopuszczalności. $v$

Nie ma problemu z wybraniem wystarczająco dużego, aby każde cięcie z i po tej samej stronie było ujemne, ponieważ możemy wybrać tak duże, jak chcemy. Ale skąd możemy wybrać tak, że kiedy nie wiemy ? Naprawdę dobrze możemy przybliżać ... jeśli pozwolimy być sumą wag krawędzi w , znamy $d$ $u$ $v$ $d$ $a$ $f \approx -.99OPT$ $OPT$ $OPT$ $T$ $G$ $\frac{1}{2}T \leq OPT \leq T$ . So we have a fairly narrow range of values for $f$ , and we can iterate over $f$ taking all values between $-.49T$ and $-.99T$ at intervals of $0.005T$ . For one of these intervals, we are guaranteed that $f \approx -0.98 OPT$ , and so one of these iterations is guaranteed to return a good cut.

Finally, we need to check that the new graph has edge weights whose sum is positive. We started with a graph whose edge weights had sum $T$ , and added $f$ to the sum of the edge weights. Since $-.99T \leq f \leq -.49T$ , we're O.K.

— Peter Shor
źródło

But what are your

u $u$ and

v $v$ ? The usual formulation of the max-cut problem does not have any "special nodes" that need to be separated.

— Jukka Suomela

Hi Ian -- I don't think that works though. Why do there necessarily have to exist any

u $u$ and

v $v$ that are separated by the max-cut in the original graph, and remain separated by the max-cut after a heavy negative edge is added between them? Consider for example the complete graph -- adding a single, arbitrarily negative edge anywhere does not change the cut value at all.

— Aaron Roth

One issue is that if you add a negative edge between every pair of vertices, then you are modifying the value of different cuts by different amounts. (We subtract, say,

|S|⋅|S¯|⋅a $|S|\cdot|\bar{S}|\cdot a$ from the value of cut

S $S$ ). So we have the problem that the identity of the max-cut in the modified graph does not necessarily correspond to the max-cut in the original graph.

— 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 張顯之
źródło

the problem in Alon-Naor is similar but I don't think there is a ratio preserving reduction. their problem is to maximize

$x^TMy$ where

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

$M$ is an

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

$x = y$

— Sasho Nikolov

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

$x=y$ or not.

— david

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

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

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

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

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

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

$M = I-J$ , where

$J$ is the

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

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

$n/2$ , while

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

$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
źródło