Effiziente und einfache randomisierte Algorithmen, bei denen Determinismus schwierig ist

33

Ich höre oft, dass wir für viele Probleme sehr elegante randomisierte Algorithmen kennen, aber keine oder nur kompliziertere deterministische Lösungen. Ich kenne jedoch nur einige Beispiele dafür. Am prominentesten

  • Randomized Quicksort (und verwandte geometrische Algorithmen, zB für konvexe Hüllen)
  • Randomisierter Mincut
  • Polynomial Identity Testing
  • Klees Messproblem

Unter diesen scheint nur das Testen der polynomiellen Identität ohne die Verwendung von Zufälligkeit wirklich schwierig zu sein.

Kennen Sie weitere Beispiele für Probleme, bei denen eine zufällige Lösung sehr elegant oder sehr effizient ist, deterministische Lösungen jedoch nicht? Im Idealfall sollten die Probleme für Laien leicht zu motivieren sein (im Gegensatz zu zB polynomiellen Identitätsprüfungen).

adrianN
quelle
10
Ein weiteres Beispiel ist das Testen der Primalität. Die probabilistischen Primärtests nach Miller-Rabin und Solovay-Strassen sind sehr einfach und effizient. Es war ein seit langem offenes Problem, einen effizienten deterministischen Primalitätstest zu finden, der von Agrawal, Kayal und Saxena gelöst wurde. Der AKS-Test ist ein deterministischer Polynomtest-Primärtest. Es ist jedoch nicht so einfach und nicht so effizient wie probabilistische Tests.
Jury
8
Die randomisierte Auswahl (Medianwert) ist etwas einfacher als deterministisch. Randomisierte Algorithmen zum ungefähren Lösen von Pack- und Covering-LPs sind (im schlimmsten Fall) schneller als ihre deterministischen Gegenstücke ( KY07 , GK95 ). Viele Online-Probleme haben Algen randomisiert, die wettbewerbsfähiger sind als jeder deterministische Algorithmus FK91 .
Neal Young
11
Die Berechnung des Volumens eines konvexen Körpers in hohen Dimensionen erlaubt eine -Angleichung über Randomisierung. Es ist bekannt, dass kein deterministischer Algorithmus eine gute Annäherung liefern kann. Daher ist Randomisierung hier unerlässlich. (1+ϵ)
Chandra Chekuri 20.11.12
5
@ChandraChekuri, das ist ein guter Kommentar und wäre eine noch bessere Antwort :)
Suresh Venkat
3
@ChandraChekuri im Orakelmodell, ansonstenBPPP
Sasho Nikolov

Antworten:

36

Muttern und Schrauben sortieren

Das folgende Problem wurde 1992 von Rawlins vorgeschlagen: Angenommen, Sie erhalten eine Sammlung von n Muttern und n Schrauben. Jede Schraube passt genau auf eine Mutter. Andernfalls haben die Schrauben und Muttern unterschiedliche Größen. Die Größen sind zu eng, um einen direkten Vergleich zwischen Schraubenpaaren oder Mutternpaaren zu ermöglichen. Sie können jedoch jede Mutter mit jeder Schraube vergleichen, indem Sie versuchen, sie zusammenzuschrauben. In konstanter Zeit werden Sie feststellen, ob der Bolzen zu groß, zu klein oder genau richtig für die Mutter ist. Ihre Aufgabe ist es, herauszufinden, welche Schraube zu jeder Mutter passt, oder die Schrauben nach Größe zu sortieren.

Eine einfache Variante der randomisierten Quicksortierung löst das Problem mit hoher Wahrscheinlichkeit in -Zeit. Wähle eine zufällige Schraube aus. Verwenden Sie es, um die Nüsse zu trennen. Verwenden Sie die passende Mutter, um die Schrauben zu unterteilen. und rekursieren. Es ist jedoch nicht trivial , einen deterministischen Algorithmus zu finden, der sogar in o ( n 2 ) abläuft . Deterministische O ( n log n ) -Zeit-Algorithmen wurden schließlich 1995 von Bradford und unabhängig von Komlós, Ma und Szemerédi gefunden. Unter der Haube verwenden beide Algorithmen Varianten des AKS-Parallelsortierungsnetzwerks, also die versteckte Konstante in O ( nO(nlogn)o(n2)O(nlogn) zeitliche Begrenzung ist ziemlich groß; Die versteckte Konstante für den randomisierten Algorithmus ist 4.O(nlogn)

  • Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar und Rafail Ostrovsky. Passende Schrauben und Muttern. Proc. 5th Ann. ACM-SIAM Symp. Discrete Algorithms , 690–696, 1994.
  • Noga Alon, Phillip G. Bradford und Rudolf Fleischer. Passende Schrauben und Muttern schneller. Informieren. Proc. Lette. 59 (3): 123–127, 1996.
  • Phillip G. Bradford. Passende Schrauben und Muttern optimal. Technik. 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 und Rudolf Fleischer. Passende Schrauben und Muttern schneller. Proc. 6th. Int. Symp. Algorithmen Comput. , 402–408, 1995. Lecture Notes Comput. Sci. 1004.
  • János Komlós, Yuan Ma und Endre Szemerédi. Passende Schrauben und Muttern in . SIAM J. Discrete Math. 11 (3): 347–372, 1998.O(nlogn)
  • Gregory J. E. Rawlins. Verglichen mit was? : Eine Einführung in die Analyse von Algorithmen . Computer Science Press / WH Freeman, 1992.
Jeffε
quelle
2
Dies ist ein schönes Beispiel, aber es ist ein Orakelproblem. Gibt es eine Möglichkeit, das Orakel davon zu entfernen?
Peter Shor
Hast du einen Link zur Zeitung von 98 Szemeredi? Wie ist das schwer? Vergleichen Sie parallel jede Schraube mit einer einzigartigen Mutter und ordnen Sie jedes Paar in sortierter Reihenfolge an. übereinstimmende Elemente entfernen. In log (n) -Schritten werden die sortierten nbnbnbnbnb-Sequenzen zusammengeführt, um Übereinstimmungen zu entfernen, sobald sie auftreten. BEARBEITEN: Ja, die Nichtvergleichbarkeit von nnn- und bbbb-Zeichenfolgen ist beim Zusammenführen ärgerlich.
Chad Brewbaker
@ChadBrewbaker Angenommen, in jedem Paar außer einem ist die Schraube kleiner als die Mutter. (Ja, das ist möglich.) Was macht Ihr Algorithmus nun? Mit anderen Worten, "nervig" = "das ganze Problem".
Jeffs
Ich suchte nach dem Szemeredi-Papier und dachte laut nach, wie schwer es ist. Ja, ich stimme zu, dass ein auf Zusammenführung basierender Ansatz nicht trivial ist. Aber Vishkins Artikel über die Konnektivität paralleler Graphen hinterlassen das Gefühl, dass dies nicht unmöglich ist.
Chad Brewbaker
Mit jedem Vergleich von einer Mutter und einer Schraube erhalten Sie eine gerichtete Kante, die dem Diagramm hinzugefügt wird, oder eine Übereinstimmung, die beide Scheitelpunkte entfernt. Das Ziel wäre, verbundene Komponenten so zusammenzuführen, dass sie alle Übereinstimmungen mit einem linearen Arbeitsaufwand zusammenfassen und die Speichergröße der Kanten in einer verbundenen Komponente an den linearen Raum gebunden bleibt.
Chad Brewbaker
17

Wenn Sie nicht nur von Poly-Time sprechen, sondern sich die vielen Rechenmodelle ansehen, die wir untersuchen, gibt es überall Beispiele:

In Logspace: Ungesteuerte ST-Konnektivität (in RL seit 1979 und in L nur seit 2005)

In NC: Finden einer perfekten Übereinstimmung in einem zweigliedrigen Graphen parallel (in RNC und immer noch nicht in NC bekannt)

In interaktiven Beweisen: Deterministische geben NP, während randomisierte PSPACE können. Verwandte Themen: Um einen Proof deterministisch zu prüfen, müssen Sie sich alle Proofs ansehen, während Sie mit PCP-Proofs nur eine konstante Anzahl von Bits prüfen können.

In Algorithmic Mechanism Design: Viele randomisierte, wahrheitsgemäße Approximationsmechanismen ohne deterministisches Gegenstück.

In Kommunikationskomplexität: Die Gleichheitsfunktion erfordert eine deterministische, aber logarithmische (oder, abhängig vom genauen Modell, konstante) lineare Kommunikation nach dem Zufallsprinzip.

In Entscheidungsbäumen: Die Auswertung eines And-Or-Baums erfordert deterministische lineare Abfragen, bei der Randomisierung jedoch viel weniger. Dies entspricht im Wesentlichen der Alpha-Beta-Bereinigung, die einen randomisierten sublinearen Algorithmus für die Auswertung des Spielbaums liefert.

In Streaming-Modellen verteilte Computermodelle: Siehe vorherige Antworten.

Noam
quelle
12

Die meisten Streaming-Algorithmen

Im Streaming-Modell der Berechnung ( AMS , Buch ) verarbeitet ein Algorithmus eine Online-Sequenz von Aktualisierungen und ist darauf beschränkt, nur den sublinearen Speicherplatz beizubehalten. Zu jedem Zeitpunkt sollte der Algorithmus in der Lage sein, eine Anfrage zu beantworten.

tit[n]Dm=|{it:t=1m}|mΩ(n)O(logn)O(1ϵ2+logn)1±ϵ

Sasho Nikolov
quelle
8

nΔmin(Ω(logΔ),Ω(logn))

u

  1. u1/dudu>0udu=0u
  2. uu
  3. v

O(logn)O(n1/logn)


[1] Michael Luby: Ein einfacher paralleler Algorithmus für das Problem der maximalen unabhängigen Menge. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074

[2] Alessandro Panconesi, Aravind Srinivasan: Über die Komplexität der Zerlegung verteilter Netzwerke. J. Algorithms 20 (2): 356-374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017

[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Lokale Berechnung: Untere und obere Schranken. AdRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

Peter
quelle
Ein neuerer Algorithmus (auf der PODC 2013), der von biologischen Systemen inspiriert wurde, erzielt eine Leistung, die der von Luby vergleichbar ist, indem er einen einfachen lokalen Rückkopplungsmechanismus verwendet. arxiv.org/abs/1211.0235
András Salamon
6

Führerwahl in einem anonymen Ring von Prozessen

1

Es gibt ein einfaches Argument (zB [1]), dass es für einen anonymen Ring keinen deterministischen Wahlalgorithmus für Anführer gibt .

Modell: Wir nehmen an, dass die Berechnung in synchronen Runden fortschreitet, in denen in jeder Runde jeder Prozess eine lokale Berechnung durchführt, Nachrichten an seine Nachbarn im Ring sendet und Nachrichten von seinen Nachbarn empfängt.

Ar01

r0rArrr+1A

An[1,n4]


[1] Dana Angluin: Lokale und globale Eigenschaften in Netzwerken von Prozessoren (Extended Abstract). STOC 1980: 82 & ndash; 93. http://doi.acm.org/10.1145/800141.804655

Peter
quelle
6

Mehrheitsproblem in einem Abfragemodell.

nij

n/2O(n)

O(n)

FRK Chung, RL Graham, J. Mao und AC Yao, Oblivious und adaptive Strategien für die Mehrheits- und Pluralitätsprobleme, Proc. COCOON 2005 , S. 329–338.

Jagadisch
quelle