Randomisierter Algorithmus - Randomized algorithm

Ein randomisierter Algorithmus ist ein Algorithmus , der einen gewissen Grad an Zufälligkeit als Teil seiner Logik oder Prozedur verwendet. Der Algorithmus verwendet typischerweise gleichmäßig zufällige Bits als Hilfseingang, um sein Verhalten zu lenken, in der Hoffnung, im "Durchschnittsfall" eine gute Leistung über alle möglichen Zufallsauswahlen, die durch die Zufallsbits bestimmt werden, zu erreichen; daher sind entweder die Laufzeit oder die Ausgabe (oder beides) Zufallsvariablen.

Man muss unterscheiden zwischen Algorithmen, die die zufällige Eingabe verwenden, damit sie immer mit der richtigen Antwort terminieren, aber die zu erwartende Laufzeit endlich ist ( Las Vegas-Algorithmen , zum Beispiel Quicksort ) und Algorithmen, die die Chance haben, ein falsches Ergebnis zu produzieren ( Monte-Carlo-Algorithmen , zum Beispiel der Monte-Carlo-Algorithmus für das MFAS- Problem) oder kein Ergebnis erzeugen, indem sie entweder einen Fehler signalisieren oder nicht terminieren. In manchen Fällen sind probabilistische Algorithmen das einzige praktische Mittel zur Lösung eines Problems.

In der allgemeinen Praxis werden randomisierte Algorithmen unter Verwendung eines Pseudozufallszahlengenerators anstelle einer echten Quelle von Zufallsbits angenähert ; eine solche Implementierung kann vom erwarteten theoretischen Verhalten und den mathematischen Garantien abweichen, die von der Existenz eines idealen echten Zufallszahlengenerators abhängen können.

Motivation

Betrachten Sie als motivierendes Beispiel das Problem, ein ' a ' in einem Array von n Elementen zu finden.

Input : Ein Array von n ≥2 Elementen, in dem die Hälfte ' a 's und die andere Hälfte ' b 's sind.

Ausgabe : Suchen Sie ein ' a ' im Array.

Wir geben zwei Versionen des Algorithmus an, einen Las Vegas-Algorithmus und einen Monte-Carlo-Algorithmus .

Las Vegas-Algorithmus:

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

Dieser Algorithmus ist mit Wahrscheinlichkeit 1 erfolgreich. Die Anzahl der Iterationen variiert und kann beliebig groß sein, aber die erwartete Anzahl der Iterationen ist

\lim_{n\to\infty}\sum_{i=1}^{n}{\frac {i}{2^{i}}}=2

Da sie konstant ist, beträgt die erwartete Laufzeit über viele Aufrufe . (Siehe Big Theta-Notation ) ${\displaystyle\Theta (1)}$

Monte-Carlo-Algorithmus:

findingA_MC(array A, n, k)
begin
    i := 0
    repeat
        Randomly select one element out of n elements.
        i := i + 1
    until i = k or 'a' is found
end

Wenn ein ' a ' gefunden wird, ist der Algorithmus erfolgreich, andernfalls schlägt der Algorithmus fehl. Nach k Iterationen ist die Wahrscheinlichkeit, ein ' a ' zu finden:

$\Pr[\textrm {find~a} ]=1-(1/2)^{k}$

Dieser Algorithmus garantiert keinen Erfolg, aber die Laufzeit ist begrenzt. Die Anzahl der Iterationen ist immer kleiner oder gleich k. Wenn k konstant ist, beträgt die Laufzeit (erwartet und absolut) . ${\displaystyle\Theta (1)}$

Randomisierte Algorithmen sind besonders nützlich, wenn es um einen böswilligen "Gegner" oder Angreifer geht, der absichtlich versucht, dem Algorithmus einen schlechten Input zu geben (siehe Worst-Case-Komplexitäts- und Wettbewerbsanalyse (Online-Algorithmus) ) wie im Gefangenendilemma . Aus diesem Grund ist die Zufälligkeit in der Kryptographie allgegenwärtig . In kryptografischen Anwendungen können Pseudozufallszahlen nicht verwendet werden, da der Gegner sie vorhersagen kann, was den Algorithmus effektiv deterministisch macht. Daher ist entweder eine Quelle für echte Zufallszahlen oder ein kryptographisch sicherer Pseudo-Zufallszahlengenerator erforderlich. Ein weiterer Bereich, in dem Zufälligkeit inhärent ist, ist das Quantencomputing .

Im obigen Beispiel gibt der Las Vegas-Algorithmus immer die richtige Antwort aus, aber seine Laufzeit ist eine Zufallsvariable. Der Monte-Carlo-Algorithmus (bezogen auf das Monte-Carlo-Verfahren zur Simulation) wird garantiert in einer Zeit abgeschlossen, die durch eine Funktion, die Eingabegröße und ihren Parameter k begrenzt werden kann , aber eine geringe Fehlerwahrscheinlichkeit zulässt . Beachten Sie, dass jeder Las Vegas-Algorithmus in einen Monte-Carlo-Algorithmus umgewandelt werden kann (über die Markov-Ungleichung ), indem er eine willkürliche, möglicherweise falsche Antwort ausgibt, wenn er nicht innerhalb einer bestimmten Zeit abgeschlossen wird. Umgekehrt kann, wenn ein effizientes Verifizierungsverfahren existiert, um zu überprüfen, ob eine Antwort richtig ist, ein Monte-Carlo-Algorithmus in einen Las-Vegas-Algorithmus umgewandelt werden, indem der Monte-Carlo-Algorithmus wiederholt ausgeführt wird, bis eine richtige Antwort erhalten wird.

Rechenkomplexität

Die Computational Complexity Theory modelliert randomisierte Algorithmen als probabilistische Turing-Maschinen . Es werden sowohl Las Vegas- als auch Monte-Carlo-Algorithmen betrachtet und mehrere Komplexitätsklassen untersucht. Die grundlegendste randomisierte Komplexitätsklasse ist RP , das ist die Klasse von Entscheidungsproblemen, für die es einen effizienten (polynomielle Zeit) randomisierten Algorithmus (oder probabilistische Turing-Maschine) gibt, der NEIN-Instanzen mit absoluter Sicherheit erkennt und JA-Instanzen mit einer Wahrscheinlichkeit erkennt von mindestens 1/2. Die Komplementklasse für RP ist Co-RP. Problemklassen mit (möglicherweise nicht terminierenden) Algorithmen mit polynomialer Zeitmittelwert-Falllaufzeit, deren Ausgabe immer korrekt ist, heißen in ZPP .

Die Klasse von Problemen, für die sowohl JA- als auch NEIN-Instanzen mit einem gewissen Fehler identifiziert werden dürfen, wird BPP genannt . Diese Klasse fungiert als das randomisierte Äquivalent von P , dh BPP repräsentiert die Klasse der effizienten randomisierten Algorithmen.

Geschichte

Historisch gesehen war der erste randomisierte Algorithmus eine Methode, die von Michael O. Rabin für das Problem der nächsten Paare in der Computergeometrie entwickelt wurde . Das Studium randomisierter Algorithmen wurde durch die Entdeckung eines randomisierten Primalitätstests (dh die Bestimmung der Primalität einer Zahl) von Robert M. Solovay und Volker Strassen im Jahr 1977 vorangetrieben . Kurz darauf zeigte Michael O. Rabin, dass der Primalitätstest von 1976 von Miller in einen randomisierten Algorithmus umgewandelt werden kann. Zu dieser Zeit war kein praktischer deterministischer Algorithmus für Primalität bekannt.

Der Miller-Rabin-Primalitätstest beruht auf einer binären Beziehung zwischen zwei positiven ganzen Zahlen k und n , die ausgedrückt werden kann, indem man sagt, dass k "ein Zeuge für die Zusammengesetztheit von" n ist . Es kann gezeigt werden, dass

Wenn es einen Zeugen für die Zusammensetzbarkeit von n gibt , dann ist n zusammengesetzt (dh n ist keine Primzahl ), und
Wenn n zusammengesetzt ist, dann sind mindestens drei Viertel der natürlichen Zahlen kleiner als n Zeugen seiner Zusammengesetztheit, und
Es gibt einen schnellen Algorithmus, der bei gegebenem k und n feststellt, ob k ein Zeuge für die Zusammengesetztheit von n ist .

Beachten Sie, dass dies impliziert, dass das Primalitätsproblem in Co- RP liegt .

Wenn man zufällig 100 Zahlen kleiner als eine zusammengesetzte Zahl n wählt , dann beträgt die Wahrscheinlichkeit, einen solchen "Zeugen" nicht zu finden, (1/4) ^100, so dass dies für die meisten praktischen Zwecke ein guter Primalitätstest ist. Wenn n groß ist, gibt es möglicherweise keinen anderen praktischen Test. Die Fehlerwahrscheinlichkeit kann durch genügend unabhängige Tests beliebig reduziert werden.

Daher ist in der Praxis mit dem Akzeptieren einer kleinen Fehlerwahrscheinlichkeit kein Nachteil verbunden, da die Fehlerwahrscheinlichkeit mit ein wenig Sorgfalt astronomisch klein gemacht werden kann. Obwohl inzwischen ein deterministischer Primalitätstest in Polynomialzeit gefunden wurde (siehe AKS-Primalitätstest ), hat er die älteren probabilistischen Tests in kryptographischer Software nicht ersetzt und wird dies auch in absehbarer Zukunft nicht tun.

Beispiele

Schnelle Sorte

Quicksort ist ein bekannter, häufig verwendeter Algorithmus, bei dem Zufälligkeit nützlich sein kann. Viele deterministische Versionen dieses Algorithmus benötigen O ( n ² ) Zeit, um n Zahlen nach einer wohldefinierten Klasse von entarteten Eingaben (wie einem bereits sortierten Array) zu sortieren, wobei die spezifische Klasse von Eingaben, die dieses Verhalten erzeugen, durch das Protokoll definiert ist für Drehpunktauswahl. Wenn der Algorithmus jedoch gleichförmig zufällig Pivotelemente auswählt, hat er eine nachweislich hohe Wahrscheinlichkeit, in O ( n log n ) Zeit fertig zu werden, unabhängig von den Eigenschaften der Eingabe.

Randomisierte inkrementelle Konstruktionen in der Geometrie

In der Computergeometrie besteht eine Standardtechnik zum Bauen einer Struktur wie einer konvexen Hülle oder der Delaunay-Triangulation darin, die Eingabepunkte zufällig zu permutieren und sie dann nacheinander in die vorhandene Struktur einzufügen. Die Randomisierung stellt sicher, dass die zu erwartende Anzahl von Strukturänderungen durch eine Einfügung gering ist und somit die zu erwartende Laufzeit des Algorithmus nach oben begrenzt werden kann. Diese Technik wird als randomisierte inkrementelle Konstruktion bezeichnet .

Mindestschnitt

Eingabe : Ein Diagramm G ( V , E )

Output : A geschnitten Aufteilen die Vertices in L und R , mit der minimalen Anzahl von Kanten zwischen L und R .

Denken Sie daran, dass die Kontraktion zweier Knoten, u und v , in einem (Multi-)Graphen einen neuen Knoten u ' mit Kanten ergibt , die die Vereinigung der Kanten sind, die entweder auf u oder v auftreffen , außer bei Kanten, die u . verbinden und v . Abbildung 1 zeigt ein Beispiel des Zusammenziehens des Scheitels A und B . Nach der Kontraktion kann der resultierende Graph parallele Kanten haben, enthält jedoch keine Selbstschleifen.

Abbildung 2: Erfolgreicher Lauf des Karger-Algorithmus auf einem 10-Vertex-Graphen. Der Mindestschnitt hat die Größe 3 und wird durch die Scheitelfarben angezeigt.

Abbildung 1: Kontraktion von Scheitelpunkt A und B

Der grundlegende Algorithmus von Karger:

begin
    i = 1
    repeat
        repeat
            Take a random edge (u,v) ∈ E in G
            replace u and v with the contraction u'
        until only 2 nodes remain
        obtain the corresponding cut result C_i
        i = i + 1
    until i = m
    output the minimum cut among C₁, C₂, ..., C_m.
end

Bei jeder Ausführung der äußeren Schleife wiederholt der Algorithmus die innere Schleife, bis nur noch 2 Knoten übrig sind, der entsprechende Schnitt wird erhalten. Die Laufzeit einer Ausführung beträgt , und n bezeichnet die Anzahl der Scheitelpunkte. Nach m- maliger Ausführung der äußeren Schleife geben wir den minimalen Schnitt unter allen Ergebnissen aus. Abbildung 2 zeigt ein Beispiel für eine Ausführung des Algorithmus. Nach der Ausführung erhalten wir einen Schnitt der Größe 3. $O(n)$

Lemma 1 — Sei k die minimale Schnittgröße und sei $C = {e 1, e 2, ..., e k}$ der minimale Schnitt. Wenn während der Iteration i , keine Kante $e \in C$ für die Kontraktion ausgewählt ist, $C i = C$ .

Beweis —

Wenn G nicht zusammenhängend ist, kann G ohne Kante in L und R zerlegt werden. Der Min-Schnitt in einem nicht zusammenhängenden Graphen ist also 0. Nehmen wir nun an, G sei zusammenhängend. Sei $V = L \cup R$ die durch $C$ induzierte Partition von V $:$ $C$ $= { {$ $u$ $,$ $v$ $} \in$ $E$ $:$ $u$ $\in$ $L$ $,$ $v$ $\in$ $R$ $}$ (wohldefiniert, da G zusammenhängend ist). Betrachten Sie eine Kante { u , v } von C . Anfänglich sind u , v verschiedene Knoten. Solange wir eine Kante auswählen , werden $u$ und $v$ nicht verschmolzen. Somit haben wir am Ende des Algorithmus zwei zusammengesetzte Knoten, die den gesamten Graphen abdecken, einer besteht aus den Ecken von L und der andere besteht aus den Ecken von R . Wie in Abbildung 2 ist die Größe von min cut 1 und C = {( A , B )}. Wenn wir ( A , B ) für die Kontraktion nicht auswählen , können wir den minimalen Schnitt erhalten. $f\neq e$

Lemma 2 — Wenn G ein Multigraph mit p Ecken ist und dessen min Schnitt die Größe k hat , dann hat G mindestens pk /2 Kanten.

Beweis —

Da der minimale Schnitt k ist , muss jede Ecke v Grad( v ) k erfüllen . Daher beträgt die Summe des Grades mindestens pk . Aber es ist bekannt, dass die Summe der Scheitelgrade gleich 2| E |. Es folgt das Lemma.

Analyse des Algorithmus

Die Wahrscheinlichkeit, dass der Algorithmus erfolgreich ist, ist 1 − die Wahrscheinlichkeit, dass alle Versuche fehlschlagen. Durch Unabhängigkeit ist die Wahrscheinlichkeit, dass alle Versuche fehlschlagen,

\prod_{i=1}^{m}\Pr(C_{i}\neq C)=\prod_{i=1}^{m}(1-\Pr(C_{i}= C)).

Nach Lemma 1 ist die Wahrscheinlichkeit, dass $C i = C$ ist, die Wahrscheinlichkeit, dass während der Iteration i keine Kante von C ausgewählt wird . Betrachten Sie die innere Schleife und bezeichne $G$ $j$ den Graphen nach j Kantenkontraktionen, wobei $j$ $\in {0, 1, \dots,$ $n$ $- 3}$ . $G$ $j$ hat $n$ $-$ $j$ Ecken. Wir verwenden die Kettenregel der bedingten Möglichkeiten . Die Wahrscheinlichkeit, dass die bei Iteration j gewählte Kante nicht in C liegt , da zuvor keine Kante von C gewählt wurde, beträgt . Beachten Sie, dass $G$ $j$ immer noch einen minimalen Schnitt der Größe k hat , also nach Lemma 2 immer noch mindestens Kanten hat. $1-{\frac {k}{|E(G_{j})|}}$ ${\frac {(nj)k}{2}}$

Also, . $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{nj}}={\frac {nj-2}{nj}}$

Nach der Kettenregel ist die Wahrscheinlichkeit, den minimalen Schnitt C zu finden, also

\Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}} \right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2} {4}}\right)\left({\frac {1}{3}}\right).

Stornierung gibt . Somit beträgt die Wahrscheinlichkeit, dass der Algorithmus erfolgreich ist, mindestens . Für ist dies gleichbedeutend mit . Der Algorithmus findet den Mindestschnitt mit Wahrscheinlichkeit rechtzeitig . $\Pr[C_{i}=C]\geq {\frac{2}{n(n-1)}}$ $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ $m={\frac {n(n-1)}{2}}\ln n$ $1-{\frac {1}{n}}$ $1-{\frac {1}{n}}$ $O(mn)=O(n^{3}\log n)$

Derandomisierung

Der Zufall kann wie Raum und Zeit als Ressource betrachtet werden. Derandomization ist dann der Prozess , den Zufall zu beseitigen (oder so wenig wie möglich davon zu verwenden). Es ist derzeit nicht bekannt, ob alle Algorithmen derandomisiert werden können, ohne ihre Laufzeit signifikant zu erhöhen. In der Rechenkomplexität ist es beispielsweise unbekannt, ob P = BPP , dh wir wissen nicht, ob wir einen beliebigen randomisierten Algorithmus, der in polynomieller Zeit mit einer kleinen Fehlerwahrscheinlichkeit läuft, nehmen und ihn ohne Verwendung von Zufälligkeit auf polynomiale Zeit derandomisieren können .

Es gibt spezifische Methoden, die verwendet werden können, um bestimmte randomisierte Algorithmen zu derandomisieren:

die Methode der bedingten Wahrscheinlichkeiten und ihre Verallgemeinerung, pessimistische Schätzer
Diskrepanztheorie (die zur Derandomisierung geometrischer Algorithmen verwendet wird)
die Ausnutzung der begrenzten Unabhängigkeit der vom Algorithmus verwendeten Zufallsvariablen, wie z. B. die paarweise Unabhängigkeit, die beim universellen Hashing verwendet wird
die Verwendung von Expander-Graphen (oder Dispergierern im Allgemeinen), um eine begrenzte Menge an anfänglicher Zufälligkeit zu verstärken (dieser letzte Ansatz wird auch als Generieren von Pseudozufallsbits aus einer Zufallsquelle bezeichnet und führt zum verwandten Thema der Pseudozufälligkeit)
Ändern des randomisierten Algorithmus, um eine Hash-Funktion als Zufallsquelle für die Aufgaben des Algorithmus zu verwenden, und dann Derandomisierung des Algorithmus durch Brute-Force-Verfahren aller möglichen Parameter (Seeds) der Hash-Funktion. Diese Technik wird normalerweise verwendet, um einen Stichprobenraum erschöpfend zu durchsuchen und den Algorithmus deterministisch zu machen (z. B. randomisierte Graphalgorithmen).

Wo Zufall hilft

Wenn das Berechnungsmodell auf Turing-Maschinen beschränkt ist , ist es derzeit eine offene Frage, ob die Fähigkeit, zufällige Entscheidungen zu treffen, es ermöglicht, einige Probleme in polynomieller Zeit zu lösen, die ohne diese Fähigkeit nicht in polynomieller Zeit gelöst werden können; dies ist die Frage, ob P = BPP. In anderen Kontexten gibt es jedoch spezifische Beispiele für Probleme, bei denen die Randomisierung zu strikten Verbesserungen führt.

Basierend auf dem anfänglichen motivierenden Beispiel: Bei einer exponentiell langen Zeichenfolge von 2 ^k Zeichen, halb a und halb b, benötigt eine Maschine mit wahlfreiem Zugriff im schlimmsten Fall 2 ^{k −1} Lookups, um den Index von an a zu finden ; wenn es erlaubt ist, zufällige Entscheidungen zu treffen, kann es dieses Problem in einer erwarteten polynomialen Anzahl von Lookups lösen.
Der natürliche Weg, eine numerische Berechnung in eingebetteten Systemen oder Cyber-Physical-Systemen durchzuführen, besteht darin, ein Ergebnis zu liefern, das sich mit hoher Wahrscheinlichkeit dem richtigen annähert (oder wahrscheinlich ungefähr korrekte Berechnung (PACC)). Das schwierige Problem, das mit der Bewertung des Diskrepanzverlusts zwischen der approximierten und der korrekten Berechnung verbunden ist, kann effektiv durch Randomisierung angegangen werden
Bei der Kommunikationskomplexität kann die Gleichheit von zwei Strings bis zu einer gewissen Zuverlässigkeit unter Verwendung von Kommunikationsbits mit einem randomisierten Protokoll überprüft werden . Jedes deterministische Protokoll erfordert Bits, wenn es sich gegen einen starken Gegner verteidigt. $\log n$ ${\displaystyle\Theta(n)}$
Das Volumen eines konvexen Körpers kann durch einen randomisierten Algorithmus mit beliebiger Genauigkeit in polynomieller Zeit geschätzt werden. Bárány und Füredi zeigten, dass kein deterministischer Algorithmus das Gleiche kann. Dies gilt unbedingt, dh ohne komplexitätstheoretische Annahmen, vorausgesetzt, der konvexe Körper kann nur als Blackbox abgefragt werden.
Ein eher komplexitätstheoretisches Beispiel für einen Ort, an dem Zufälligkeit zu helfen scheint, ist die Klasse IP . IP besteht aus allen Sprachen, die (mit hoher Wahrscheinlichkeit) durch eine polynomiell lange Interaktion zwischen einem allmächtigen Beweiser und einem Verifizierer, der einen BPP-Algorithmus implementiert, akzeptiert werden können. IP = PSPACE . Wenn es jedoch erforderlich ist, dass der Verifizierer deterministisch ist, dann gilt IP = NP .
In einem chemischen Reaktionsnetzwerk (einer endlichen Reihe von Reaktionen wie A+B → 2C + D, die auf eine endliche Anzahl von Molekülen wirken) ist die Fähigkeit, von einem Anfangszustand aus jemals einen bestimmten Zielzustand zu erreichen, entscheidbar, während die Wahrscheinlichkeit von jemals einen bestimmten Zielzustand zu erreichen (unter Verwendung der standardmäßigen konzentrationsbasierten Wahrscheinlichkeit, für welche Reaktion als nächstes auftritt) ist unentscheidbar. Genauer gesagt kann eine begrenzte Turingmaschine mit beliebig hoher Wahrscheinlichkeit für alle Zeit korrekt simuliert werden, nur wenn ein zufälliges chemisches Reaktionsnetzwerk verwendet wird. Bei einem einfachen nichtdeterministischen chemischen Reaktionsnetzwerk (jede mögliche Reaktion kann als nächstes ablaufen) ist die Rechenleistung auf primitive rekursive Funktionen beschränkt .

Siehe auch

Anmerkungen

Verweise

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , Zweite Auflage. MIT Press und McGraw-Hill, 1990. ISBN 0-262-03293-7 . Kapitel 5: Wahrscheinlichkeitsanalyse und randomisierte Algorithmen, S. 91–122.
Dirk Draheim. " Semantik des probabilistisch typisierten Lambda-Kalküls (Markov Chain Semantics, Termination Behavior, and Denotational Semantics). " Springer, 2017.
Jon Kleinberg und Eva Tardos . Algorithmus-Design . Kapitel 13: "Randomisierte Algorithmen".
Fallis, D. (2000). „Die Zuverlässigkeit von randomisierten Algorithmen“. Das britische Journal für Wissenschaftsphilosophie . 51 (2): 255–271. doi : 10.1093/bjps/51.2.255 .
M. Mitzenmacher und E. Upfal . Wahrscheinlichkeit und Berechnung: Randomisierte Algorithmen und Wahrscheinlichkeitsanalyse . Cambridge University Press, New York (NY), 2005.
Rajeev Motwani und P. Raghavan. Randomisierte Algorithmen . Cambridge University Press, New York (NY), 1995.
Rajeev Motwani und P. Raghavan. Randomisierte Algorithmen . Eine Umfrage zu randomisierten Algorithmen.
Christos Papadimitriou (1993), Computational Complexity (1. Aufl.), Addison Wesley, ISBN 978-0-201-53082-7 Kapitel 11: Randomisierte Berechnung, S. 241–278.
Rabin, Michael O. (1980). "Probabilistischer Algorithmus zum Testen der Primalität" . Zeitschrift für Zahlentheorie . 12 : 128–138. doi : 10.1016/0022-314X(80)90084-0 .
AA Tsay, WS Lovejoy, David R. Karger, Random Sampling in Cut, Flow und Network Design Problems , Mathematics of Operations Research, 24(2):383–413, 1999.

Languages

In other projects