Max-cut z ujemnymi krawędziami wagi

35

G=(V,E,w)w:ERarg max S V ( u , v ) E : u S , v S w ( u , v ) w ( e ) 0 e E

argmaxSV(u,v)E:uS,vSw(u,v)
w(e)0eE
  1. Odbiór losowego podzbioru wierzchołki .S.S
  2. Wybierz kolejność na wierzchołkach i łapczywie umieść każdy wierzchołek w lub aby zmaksymalizować do tej pory przycięte krawędziev S ˉ SvSS¯
  3. 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 ˉ SSS¯

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

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 e E w ( e ) > 00eEw(e)>0

Aaron Roth
źródło
1
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 N P . PNP
Aaron Roth,

Odpowiedzi:

28

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 b . Teraz umieść dużą ujemną krawędź wagi (o wadze - a ) między u i v . Optymalnym rozwiązaniem nowego problemu jest b - a , więc nasz hipotetyczny algorytm aproksymacyjny dostarczy Ci rozwiązanie z maksymalnym cięciem, którego wartość jest co najwyżej ( b - a ) / 2 gorsza niż optymalna. Na oryginalnym wykresie maksymalne cięcie jest nadal co najwyżejbauvba(ba)/2 ( b - a ) / 2(ba)/2 gorsze niż optymalne. Jeśli zdecydujesz się blisko B , ten jest niezgodny wynik inapproximability że jeśli P NP, nie można przybliżona maksymalna kroju lepiej niż 16 / 17 czynnika. ab16/17

EDYTOWAĆ:

Powyższy algorytm nie działa, ponieważ nie można zagwarantować, że u i v 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.uv

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 G ze wszystkimi nieujemnymi wagami na krawędziach. Znajdziemy zmodyfikowany wykres G z pewnymi ujemnymi wagami, tak że jeśli będziemy w stanie przybliżać maksymalne cięcie G GGG ze współczynnikiem 2, możemy bardzo dobrze przybliżać maksymalne cięcie G.G

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

Redukcja o wartości C na G , w którym wierzchołki U i V są po tej samej stronie cięcia, teraz wartości w ° C - 2 d, m , gdzie m jest liczbą wierzchołków na drugiej stronie cięcia. Cięcie z ( u , v ) po przeciwnych stronach o pierwotnej wartości c ma teraz wartość c + a - ( n - 2 ) d . Zatem jeśli wybieramy d wystarczająco duże, możemy wymusić wszystkie cięcia za pomocą u i vcGuvc2dmm(u,v)cc+a(n2)dduvpo 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 G będzie miało u i v po przeciwnych stronach. Zauważ, że dodajemy stały ciężar ( a - ( n - 2 ) d ) do każdego cięcia za pomocą u i v po przeciwnych stronach.Guv(a(n2)d)uv

Niech f = ( a - ( n - 2 ) d ) . Wybierz tak, że f - 0,98 O P T (będziemy usprawiedliwiać tym później). Redukcja o masie C na G o u i v w przeciwnych stronach się teraz cięte z masy c - 0,98 O P T . Oznacza to, że optymalne cięcie w G ma wagę 0,02 O P Tf=(a(n2)d)af0.98OPTcGuvc0.98OPTG0.02OPT . Nasz nowy algorytm znajduje cięcie w G Go masie co najmniej 0,01 O P T . Przekłada się to na cięcie na oryginalnym wykresie G o wadze co najmniej 0,99 O P T (ponieważ wszystkie cięcia w G o dodatniej wadze oddzielają u i0.01OPTG0.99OPTGu v ), co jest lepsze niż wynik niedopuszczalności.v

Nie ma problemu z wybraniem d wystarczająco dużego, aby każde cięcie z u i v po tej samej stronie było ujemne, ponieważ możemy wybrać d tak duże, jak chcemy. Ale skąd możemy wybrać tak, że f - .99 O P T kiedy nie wiemy O P T ? Naprawdę dobrze możemy przybliżać O P T ... jeśli pozwolimy T być sumą wag krawędzi w G , znamy 1duvdaf.99OPTOPTOPTTG2TOPTT12TOPTT. So we have a fairly narrow range of values for ff, and we can iterate over ff taking all values between .49T.49T and .99T.99T at intervals of 0.005T0.005T. For one of these intervals, we are guaranteed that f0.98OPTf0.98OPT, 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 TT, and added ff to the sum of the edge weights. Since .99Tf.49T.99Tf.49T, we're O.K.

Peter Shor
źródło
1
But what are your uu and vv? The usual formulation of the max-cut problem does not have any "special nodes" that need to be separated.
Jukka Suomela
3
Hi Ian -- I don't think that works though. Why do there necessarily have to exist any uu and vv 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
2
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||S¯|a from the value of cut SS). 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
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 張顯之
ź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 xTMy where x,y{±1}n and M is an n×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 maxx|xTMx|maxx,yxTMy4maxx|xTMx| where all maximums are over {1,1}n, and M is symmetric with nonnegative diagonal. However, the problem maxx|xTMx| can have very different value from maxxxTMx (which is what we need for MaxCut). For example, consider M=IJ, where J is the n×n all ones matrix. You can see maxxxTMx is about n/2, while maxx|xTMx| is n2n.
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 xTMx for a n×n matrix M, where x ranges over {±1}n. MaxCut can be written in this form by setting M=12n(we)I12A where I is the identity matrix and A is the adjacency matrix. The MaxQP algorithm of Charikar and Wirth gives an O(logn) approximation for MaxQP as long as M has a non-negative diagonal. So as long as we0, MaxCut with negative weights has a logarithmic approximation.

Sasho Nikolov
źródło