Inne zastosowania wzmocnienia rozgałęzień Karger-Stein?

27

Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która doprowadzi ten punkt do domu.)

Algorytm Kargera i Steina jest udoskonaleniem wcześniejszego algorytmu Kargera, który iteracyjnie kurczy losowe krawędzie, dopóki wykres nie będzie miał tylko dwóch wierzchołków; ten prosty algorytm działa w czasie i zwraca minimalne cięcie z prawdopodobieństwem Ω ( 1 / n 2 ) , gdzie n jest liczbą wierzchołków na wykresie wejściowym. Udoskonalony „rekurencyjny algorytm skurczu” iteracyjnie kurczy losowe krawędzie, aż liczba wierzchołków spadnie z n do n / O(n2)Ω(1/n2)nn , rekurencyjnie wywołuje siędwukrotniena pozostałym wykresie i zwraca mniejsze z dwóch powstałych cięć. Prosta implementacja udoskonalonego algorytmu działa w czasieO(n2logn)i zwraca minimalne cięcie z prawdopodobieństwemΩ(1/logn). (Istnieją bardziej wydajne implementacje tych algorytmów i lepsze algorytmy losowe).n/2O(n2logn)Ω(1/logn)

Jakie inne randomizowane algorytmy wykorzystują podobne techniki wzmocnienia rozgałęziania? Szczególnie interesują mnie przykłady, które (oczywiście) nie obejmują cięć graficznych.

Jeffε
źródło
2
Ładne pytanie, Jeff!
Suresh Venkat
Czy to jest tumbleweed?
Jeffε
nie jestem pewien, co masz na myśli
Suresh Venkat
a co byś wziął za przykład wzmocnienia rozgałęziania?
Suresh Venkat
2
tumbleweed to także znaczek na tej stronie, który z pewnością nie dotyczy twojego pytania, @JeffE!
Lew Reyzin

Odpowiedzi:

5

@JeffE, tutaj jest papier, który liczy minimalne cykle wagowe na wykresie. O ile pamiętam, zdecydowanie był inspirowany techniką / wynikiem Kargera i był to zabawny dowód. Mam nadzieję, że to pomaga w nauczaniu.

V Vinay
źródło
Ten papier nie liczy liczby cykli masy minimalnej na wykresie. Zamiast tego daje ograniczenie liczby cykli, których waga jest co najwyżej stałą wielokrotnością masy cyklu minimalnego.
Tyson Williams,