Wydajne i proste randomizowane algorytmy, w których determinizm jest trudny

Często słyszę, że w przypadku wielu problemów znamy bardzo eleganckie algorytmy randomizowane, ale nie ma, lub tylko bardziej skomplikowane, deterministyczne rozwiązania. Znam jednak tylko kilka przykładów. Najbardziej widoczne

• Randomized Quicksort (i powiązane algorytmy geometryczne, np. Dla wypukłych kadłubów)
• Randomized Mincut
• Testowanie tożsamości wielomianowej
• Problem Klee'a

Spośród nich jedynie testowanie tożsamości wielomianowej wydaje się być naprawdę trudne bez użycia losowości.

Czy znasz więcej przykładów problemów, w których rozwiązanie losowe jest bardzo eleganckie lub bardzo wydajne, ale rozwiązania deterministyczne nie? Idealnie byłoby, gdyby problemy były łatwe do motywowania dla laików (w przeciwieństwie do np. Testowania tożsamości wielomianowej).

Sortowanie nakrętek i śrub

W 1992 roku Rawlins zasugerował następujący problem: Załóżmy, że otrzymałeś zbiór n nakrętek i n śrub. Każda śruba pasuje dokładnie do jednej nakrętki, w przeciwnym razie nakrętki i śruby mają różne rozmiary. Rozmiary są zbyt blisko, aby umożliwić bezpośrednie porównanie między parami śrub lub parami nakrętek. Można jednak porównać dowolną nakrętkę do dowolnej śruby, próbując je skręcić; w ciągłym czasie odkryjesz, czy śruba jest za duża, za mała, czy w sam raz dla nakrętki. Twoim zadaniem jest odkrycie, która śruba pasuje do każdej nakrętki lub równoważnie, aby posortować nakrętki i śruby według rozmiaru.

Prosty wariant losowego szybkiego sortowania rozwiązuje problem w z dużym prawdopodobieństwem. Wybierz losową śrubę; użyj go do podzielenia nakrętek; użyj pasującej nakrętki, aby rozdzielić śruby; i powtórzyć. Jednak znalezienie algorytmu deterministycznego, który działa nawet w o ( n 2 ), nie jest łatwe. Deterministycznealgorytmy czasu O ( n log n ) zostały ostatecznie znalezione w 1995 r. Przez Bradforda i niezależnie przez Komlósa, Ma i Szemerédiego. Pod maską oba algorytmy wykorzystują warianty sieci sortowania równoległego AKS, więc ukryta stała w O ( $O(n \log n)$$o(n^2)$$O(n\log n)$ ograniczenie czasowe jest dość duże; ukryta stała dla algorytmu losowego wynosi 4.$O(n\log n)$

• Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar i Rafail Ostrovsky. Pasujące nakrętki i śruby. Proc. 5th Ann. ACM-SIAM Symp. Discrete Al Algorytmy , 690–696, 1994.
• Noga Alon, Phillip G. Bradford i Rudolf Fleischer. Szybsze dopasowanie nakrętek i śrub. Poinformować. Proc. Łotysz. 59 (3): 123–127, 1996.
• Phillip G. Bradford. Optymalne dopasowanie nakrętek i śrub. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
• Phillip G. Bradford i Rudolf Fleischer. Szybsze dopasowanie nakrętek i śrub. Proc. 6. Int. Symp. Obliczanie algorytmów. , 402–408, 1995. Uwagi do wykładu Oblicz. Sci. 1004.
• János Komlós, Yuan Ma i Endre Szemerédi. Dopasowywanie nakrętek i śrub w czasie . SIAM J. Discrete Math. 11 (3): 347–372, 1998.$O(n\log n)$
• Gregory J. E. Rawlins. W porównaniu do czego? : Wprowadzenie do analizy algorytmów . Computer Science Press / WH Freeman, 1992.

Kiedy mówisz nie tylko o wielogodzinach, ale raczej przyglądasz się wielu modelom obliczeń, które badamy, wszędzie są przykłady:

W Logspace: Niekierowana łączność ST (w RL od 1979 r., Aw L tylko od 2005 r.)

W NC: Znalezienie idealnego dopasowania na dwuczęściowym wykresie równolegle (w RNC i nadal nie wiadomo, że jest w NC)

W dowodach interaktywnych: deterministyczne dają NP, podczas gdy randomizowane mogą wykonywać PSPACE. Powiązane: deterministyczne sprawdzenie dowodu wymaga spojrzenia na cały dowód, podczas gdy dowody PCP pozwalają sprawdzić tylko stałą liczbę bitów.

W projekcie mechanizmu algorytmicznego: wiele losowych, prawdziwych mechanizmów przybliżania bez deterministycznego odpowiednika.

W złożoności komunikacji: funkcja równości wymaga deterministycznej komunikacji liniowej, ale logarytmicznej (lub, w zależności od dokładnego modelu, stałej) komunikacji losowo.

W drzewach decyzyjnych: ocena drzewa i-lub wymaga deterministycznych zapytań liniowych, ale znacznie mniej z randomizacją. Jest to zasadniczo równoważne przycinaniu alfa-beta, które daje losowy algorytm sublinearny do oceny drzewa gry.

W modelach przesyłania strumieniowego modele rozproszone: patrz poprzednie odpowiedzi.

Większość algorytmów przesyłania strumieniowego

W strumieniowym modelu obliczeniowym ( AMS , książka ) algorytm przetwarza sekwencję aktualizacji online i jest ograniczony do zachowania jedynie przestrzeni sublinearnej. W dowolnym momencie algorytm powinien być w stanie odpowiedzieć na zapytanie.

Dla wielu problemów istnieją losowe algorytmy strumieniowania podliniowego w przestrzeni, podczas gdy żaden algorytm deterministyczny nie jest w stanie rozwiązać problemu w przestrzeni podliniowej. Jest to związane z lukami między losową i deterministyczną złożonością komunikacji. Prostym przykładem jest problem z odrębnym zliczaniem : za każdym razem, gdy algorytm otrzymuje liczbę całkowitą i t ∈ [ n ] , powinien być w stanie przybliżać D m = | { i t : t = 1 … m } | , tj. liczba różnych liczb całkowitych widzianych do kroku czasu $t$$i_t \in [n]$$D_m = |\{i_t: t = 1\ldots m\}|$$m$. Stosunkowo łatwo jest wykazać, że każdy algorytm deterministyczny osiągający stałe przybliżenie musi wykorzystywać przestrzeń (patrz np. Uwagi do wykładu Piotra Indyka). Z drugiej strony sprytny algorytm próbkowania Flajoleta i Martina (prosta analiza z ograniczoną losowością w powiązanym powyżej dokumencie AMS) osiąga stałe przybliżenie w bitach O ( log n ) . Najnowsze dzieło na problemie daje optymalną O ( $\Omega(n)$$O(\log n)$algorytm obliczającyprzybliżenie1±ϵ.$O(\frac{1}{\epsilon^2} + \log n)$$1\pm \epsilon$

Znalezienie maksymalną niezależny zestaw w sieci rozproszonej z węzłów, maksymalny stopień hemibursztynianu . Znana jest dolna granica [3] min ( Ω ( log Δ ) , Ω ( $n$$\Delta$który dotyczy algorytmów losowych i deterministycznych.$\min(\Omega(\log\Delta),\Omega(\sqrt{\log n}))$

Poniżej przedstawiono prosty randomizowany algorytm rozproszony [1], który przebiega w rundach synchronicznych . (W rundzie każdy węzeł $u$ można wykonywać niektórych lokalnych wiadomości obliczeń i wysłać do swoich sąsiadów. Komunikaty te są gwarantowane do odbioru przed rozpoczęciem kolejnej rundy).

1. W każdej rundzie każdy aktywny węzeł zaznacza się z prawdopodobieństwem 1 / d u, gdzie d u > 0 jest stopniem u ; jeśli d u = 0 , $u$$1/d_u$$d_u>0$$u$$d_u=0$$u$ prostu wprowadza niezależny zestaw. (Początkowo każdy węzeł jest aktywny.)
2. Jeśli jest jedynym zaznaczonym węzłem w jego sąsiedztwie, to $u$$u$ wchodzi niezależny zestaw, wyłącza się i powiadamia wszystkich swoich sąsiadów, aby wyłączyć się. Stopnie pozostałych aktywnych węzłów są odpowiednio zmniejszane, tzn. Wszystkie krawędzie dezaktywowanych węzłów są usuwane.
3. W przeciwnym razie, jeśli jakiś sąsiadujący węzeł jest również zaznaczony, wierzchołek niższego stopnia odznacza się i pozostaje aktywny.$v$

$O(\log n)$$O(n^{1/\sqrt{\log n}})$

[1] Michael Luby: Prosty algorytm równoległy dla problemu maksymalnego zestawu niezależnego. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074

[2] Alessandro Panconesi, Aravind Srinivasan: O złożoności rozproszonego rozkładu sieci. J. Al Algorytmy 20 (2): 356–374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017

[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

Wybory lidera w anonimowym pierścieniu procesów

$1$ stan . Jest to tak zwany problem wyboru lidera, który jest jednym z podstawowych zadań łamania symetrii w systemie rozproszonym i ma wiele zastosowań.

Istnieje prosty argument (np. [1]), że nie ma algorytmu deterministycznego wyboru lidera dla anonimowego pierścienia.

Model: Zakładamy, że obliczenia postępują w rundach synchronicznych, w których w każdej rundzie każdy proces wykonuje pewne obliczenia lokalne, wysyła wiadomości do swoich sąsiadów w ringu i odbiera wiadomości od swoich sąsiadów.

$A$$r\ge 0$$1$

$r\ge 0$$r$$A$$r$$r$$r+1$$A$

$A$$n$$[1,n^4]$

[1] Dana Angluin: Lokalne i globalne właściwości w sieciach procesorów (Extended Abstract). STOC 1980: 82-93. http://doi.acm.org/10.1145/800141.804655

Problem większości w modelu zapytań.

Problem . Dostajemy zestaw$n$kule barwione dwoma lub więcej kolorami. Celem jest znalezienie kuli koloru większości (tj. Koloru, który występuje więcej niż n / 2 razy) przy założeniu, że taki kolor istnieje, przy użyciu zapytań w formie „Czy piłka$i$ i piłka $j$ mieć ten sam kolor? ”. Strategia musi być nieświadoma, tzn. zapytania nie mogą zależeć od wyników poprzednich zapytań.

Algorytm losowy . Wybierz losową piłkę i sprawdź, czy więcej niż$n/2$kule mają ten sam kolor. Ten algorytm działa$O(n)$ oczekiwany czas.

Deterministyczny $O(n)$algorytm jest dość trywialny i jest przyjemną aplikacją ekspanderów.

FRK Chung, RL Graham, J. Mao i AC Yao, Nieświadome i adaptacyjne strategie na problemy większości i mnogości, Proc. COCOON 2005 , s. 329–338.