- Odbiór losowego podzbioru wierzchołki .S.
S - Wybierz kolejność na wierzchołkach i łapczywie umieść każdy wierzchołek w lub aby zmaksymalizować do tej pory przycięte krawędziev S ˉ S
v S 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 ˉ S
S 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 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 Σe∈Ew(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 ) > 0
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 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żejb −a u v b−a (b−a)/2 ( b - a ) / 2(b−a)/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. a b ≠ 16/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.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 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 ∗G G∗ G∗ 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 .u v v −d (u,x) (v,x) x≠u,v a (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 vc 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 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.G∗ u v (a−(n−2)d) u v
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−(n−2)d) a f≈−0.98OPT c G u v c−0.98OPT G∗ 0.02OPT . Nasz nowy algorytm znajduje cięcie w G ∗G∗ o 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.01OPT G 0.99OPT G∗ u 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 1d u v d a f≈−.99OPT OPT OPT T G 2T≤OPT≤T12T≤OPT≤T . 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 f≈−0.98OPTf≈−0.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 −.99T≤f≤−.49T−.99T≤f≤−.49T , we're O.K.
źródło
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
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!
źródło
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)I−12A 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 ∑we≥0, MaxCut with negative weights has a logarithmic approximation.
źródło