Algorytm Max-Cut, który nie powinien działać, nie wiadomo dlaczego

OK, może się to wydawać pytaniem o pracę domową iw pewnym sensie tak jest. Jako zadanie domowe w klasie algorytmów licencjackich podałem następujący klasyk:

Biorąc pod uwagę nieukierowany wykres , podaj algorytm, który znajdzie cięcie taki sposób, że , gdzie to liczba krawędzi przecinających cięcie. Złożoność czasowa musi wynosić .$G=(V,E)$$(S,\bar{S})$$\delta(S,\bar{S})\geq |E|/2$$\delta(S,\bar{S})$$O(V+E)$

Z jakiegoś powodu mam wiele z następujących rozwiązań. Teraz zajmuje zbyt dużo czasu, więc nie jest to kwestia oceniania, ale zainteresowałem się. To „nie wydaje się” poprawne, ale wszystkie moje próby kontrprzykładów zakończyły się niepowodzeniem. Oto on:

1. Ustaw$S\leftarrow \emptyset$
2. Niech będzie na wykresie wierzchołkiem o maksymalnym stopniu$v$
3. Dodaj do$v$$S$
4. Usuń wszystkie krawędzie sąsiadujące z$v$
5. Jeśli wróć do 2$\delta(S,\bar{S}) < |E|/2$

Zauważ, że w kroku 5 odnosi się do oryginalnego wykresu. Zauważ też, że gdybyśmy pominęli krok 4, byłoby to oczywiście błędne (na przykład połączenie trójkąta z dwiema izolowanymi krawędziami).$E$

Teraz każdy prosty dowód ma następujący problem - być może podczas dodawania nowego wierzchołka faktycznie usuwamykrawędzie wycięcia podczas dodawania nowych ( nowych krawędzi (gdzie odnosi się do wykresu z usuniętymi krawędziami). Chodzi o to, że jeśli jest to szkodliwe dla naszej sprawy, oznacza to, że ten wierzchołek „kiedyś” miał coraz wyższy stopień, więc „powinien był zostać” wybrany wcześniej.| S | d ( v ) d ( v ) $v$$|S|$$d(v)$$d(v)$$v$

Czy to dobrze znane algorytmy? Czy jest na to jakiś prosty kontrprzykład?

^{Moje wcześniejsze roszczenie z nie uwzględnia cięcia wielkościn2/4już w wykresie. Wydaje się, że następująca konstrukcja (imperialnie - stworzyłem pytanie na stronie math.stackexchange.com w celu uzyskania dokładnego dowodu) wO($\frac{2}{c+6}$$n^2/4$ułamek.$O\left(\frac{1}{\log c}\right)$}

Algorytm źle działa na połączeniach kilku odłączonych, różnej wielkości kompletnych wykresów. Cały wykres na wierzchołkach oznaczamy jako K n . Rozważ zachowanie algorytmu na K n : wielokrotnie dodaje dowolny wierzchołek jeszcze w S do S - wszystkie takie wierzchołki są identyczne, więc kolejność nie ma znaczenia. Ustawienie liczby wierzchołków jeszcze nie dodanych do S przez algorytm | ˉ S | = k , wielkość nacięcia w tym momencie wynosi k ( n - k ) .$n$$K_n$$K_n$$S$$S$$S$$|\bar{S}| = k$$k (n-k)$

Zastanów się, co się stanie, jeśli uruchomimy algorytm na kilku odłączonych grafach ze stałymi x i między 0 a 1. Jeśli k i jest liczbą elementów, które nie są jeszcze w S na i- tym kompletnym grafie, algorytm będzie wielokrotnie dodawał wierzchołkiem do S z pełnego wykresu z najwyżej k I , łamiąc związki dowolnie. Będzie to wywoływać `okrągłe” uzupełnień opartych wierzchołków do S : algorytm dodaje wierzchołek ze wszystkich graf pełny o najwyższym k = k I , a następnie ze wszystkich graf pełny z $K_{x_i n}$$x_i$$k_i$$S$$i$$S$$k_i$$S$$k = k_i$ (zaktualizacją k i po poprzedniej rundzie) i tak dalej. Gdy pełny wykres ma dodany wierzchołek do S w rundzie, będzie to robił dla każdej rundy od tego momentu.$k_i=k-1$$k_i$$S$

Niech będzie liczbą kompletnych wykresów. Niech 0 < x i ≤ 1 z 0 ≤ i ≤ c - 1 będzie modyfikatorem wielkości dla i-tego pełnego wykresu. Zamawiamy te modyfikatory wielkości od dużych do małych i ustawiamy x 0 = 1 . Mamy teraz, że jeśli istnieją wykresy c ′ z dokładnie k elementami, które nie zostały jeszcze dodane do S , wówczas wielkość nacięcia w tym czasie wynosi ∑ c ′ - 1 i = 0 k $c$$0 < x_i \leq 1$$0 \leq i \leq c - 1$$i$$x_0 = 1$$c'$$k$$S$ . Całkowita liczba krawędzi wynosi | E | = ∑ c - 1 i = 0 x i n ( x i n - 1 $\sum_{i=0}^{c'-1} k (x_i n - k) = k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$ .$|E| = \sum_{i=0}^{c-1} \frac{x_i n (x_i n - 1)}{2} \approx \frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2$

Zauważ, że jest funkcją kwadratową w k, a zatem ma maksimum. Dlatego będziemy mieli kilka lokalnych maksymalnych cięć. Na przykład, jeśli c = 1, nasze maksymalne cięcie wynosi k = $k n \sum_{i=0}^{c'-1} x_i - c' k^2$$k$$c=1$ wielkościn$k=\frac{n}{2}$ . Mamy zamiar odebraćx1tak, żex1=1/2-ε, co oznacza drugi graf pełny nie będzie zmieniać rozmiar tego lokalnie maksymalnego cięcia przyk=$\frac{n^2}{4}$$x_1$$x_1 = 1/2 - \varepsilon$ . Następnie dostać nowy lokalnie maksymalne cięcie przyk=3/8$k=\frac{n}{2}$ i tak możemy odebrać x 2 = 3 / 8 n - ε " (z ε , ε ' , ε " małych stałych). Będziemy ignorować ε s na chwilę i po prostu założyć możemy odebrać x 1 = 1 / 2 - powinniśmy zapewnić x 1 n = $k=3/8 n - \varepsilon'$$x_2 = 3/8 n - \varepsilon''$$\varepsilon, \varepsilon', \varepsilon''$$\varepsilon$$x_1 = 1/2$, ale nie wpłynie to na końcowe wyniki, jeślinjest wystarczająco duże.$x_1 n = \frac{n}{2} - 1$$n$

Chcemy znaleźć lokalne maksima naszych cięć. Rozróżniamy do k , uzyskując n ∑ c ′ - 1 i = 0 ( x i ) - 2 c ′ k . Równanie 0 daje k = $k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$$k$$n \sum_{i=0}^{c'-1} (x_i) - 2 c' k$$0$, co daje cięcie o rozmiarzen$k = \frac{n}{2c'} \sum_{i=0}^{c'-1} x_i$.$\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$

Pozwolić być k określona w poprzednim ustępie, jeżeli c ' = I . Zapewniamy, że formuła posiada żądając, że X i n < k I - wszystkie graf pełny i ' z I ' > i są wtedy mniejsze niż k í tego lokalnie maksymalnego cięcia, a tym samym nie zwiększają rozmiar cięcia. Oznacza to, że mamy c cięcia w tych k i, które są większe niż wszystkie inne cięcia znalezione przez algorytm.$k_i$$k$$c'=i$$x_i n < k_i$$i'$$i'>i$$k_i$$c$$k_i$

Wypełniając , otrzymujemy rekurencję x i = $x_i n < k_i$ (plus niektóre małe ε ) przy x 0 = 1 . Rozwiązanie tego daje x i = ( 2 $x_i = \frac{1}{2c'} \sum_{i=0}^{c'-1} x_i$$\varepsilon$$x_0 = 1$ :patrz moje pytanie na stronie math.stackexchange.comdotyczące pochodnej autorstwa @Daniela Fishera. Podłączając to don$x_i = \frac{\binom{2i}{i}}{4^i}$i wykorzystanie naszego wglądu w nawrót daje nam cięcia o rozmiarzen$\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$. Korzystając zwłaściwości tego centralnego współczynnika dwumianowego, mamylimc′→∞c′( ( 2 c $\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$ (zobacz takżemoje pytanie na stronie math.stackexchange.com).$\lim_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$

Liczba krawędzi wynosi około . Według znanych właściwościmamy$\frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2 = \frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$ . Wpisanie daje co najmniejn$\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$ który jest asymptotycznien$\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum_{i=0}^{c-1} \frac{1}{i}$jakocidzie do nieskończoności.$\frac{n^2}{8} \log c$$c$

Mamy zatem jest asymptotycznie równy$\frac{\delta(S, \bar{S})}{|E|}$ jakocprzechodzi w nieskończoność, pokazując, że algorytm może zwracać cięcia, które są dowolnie małymi ułamkami| E| .$\frac{8}{\pi \log c}$$c$$|E|$

Po chwili namysłu i zadawania pytań, oto przykład, dzięki uprzejmości Ami Paz :

Niech będzie parzyste, a G będzie wykresem będącym sumą K n z dopasowaniem n $n$$G$$K_n$ wierzchołków (to znaczy dopasowaniem z n / 2 + 1 krawędziami).$n+2$$n/2+1$

Jak działa algorytm na tym wykresie? Po prostu pobiera wierzchołki z części kliki w dowolnej kolejności. Po pobraniu wierzchołków z kliki nacięcie ma rozmiar k ⋅ ( n - k ) . Jest to maksymalne dla k = n / 2 , co daje cięcie o rozmiarze n $k$$k\cdot (n-k)$$k=n/2$ , podczas gdy liczba krawędzi na wykresie wynosin$\frac{n^2}{4}$.$\frac{n^2}{2}+1$

Algorytm zgodnie z zaleceniami będzie kontynuował dodawanie wierzchołków z kliki, zmniejszając liczbę krawędzi przecinających nacięcie, aż pozostała z kliki będzie tylko pojedynczą krawędzią. W tym momencie nie może uzyskać niczego lepszego niż .$\frac{n}{2}+2$