Andere Anwendungen der Karger-Stein-Verzweigungsverstärkung?

27

Ich habe gerade den Karger-Stein Randomized Mincut-Algorithmus in meiner Abschlussklasse unterrichtet. Dies ist ein echtes Juwel in Sachen Algorithmus , daher kann ich es nicht lehren, aber es macht mich immer frustriert, weil ich keine anderen Anwendungen der Haupttechnik kenne. (Daher ist es schwierig, Hausaufgaben zuzuweisen, die den Punkt nach Hause bringen.)

Der Algorithmus von Karger und Stein ist eine Weiterentwicklung eines früheren Algorithmus von Karger, bei dem zufällige Kanten iterativ kontrahiert werden, bis der Graph nur noch zwei Eckpunkte hat. Dieser einfache Algorithmus läuft in der Zeit und gibt einen minimalen Schnitt mit der Wahrscheinlichkeit Ω ( 1 / n 2 ) zurück , wobei n die Anzahl der Eckpunkte im Eingabegraphen ist. Der verfeinerte "Rekursive Kontraktionsalgorithmus" zieht iterativ zufällige Kanten zusammen, bis die Anzahl der Scheitelpunkte von n auf n / abfälltO(n2)Ω(1/n2)nn , ruft sichim verbleibenden Diagrammzweimalrekursivauf und gibt den kleineren der beiden resultierenden Schnitte zurück. Eine einfache Implementierung des verfeinerten Algorithmus läuft in der ZeitO(n2logn)und gibt einen minimalen Schnitt mit der WahrscheinlichkeitΩ(1/logn) zurück. (Es gibt effizientere Implementierungen dieser Algorithmen und besser randomisierte Algorithmen.)n/2O(n2Logn)Ω(1/Logn)

Welche anderen randomisierten Algorithmen verwenden ähnliche Verzweigungsverstärkungstechniken? Ich interessiere mich besonders für Beispiele, die (offensichtlich) keine Grafikschnitte beinhalten.

Jeffε
quelle
2
Gute Frage, Jeff!
Suresh Venkat
Ist das ein Tumbleweed?
Jeffs
nicht sicher, was du meinst
Suresh Venkat
Was würden Sie als Beispiel für eine Verzweigungsverstärkung ansehen?
Suresh Venkat
2
tumbleweed ist auch ein Abzeichen auf dieser Seite, was sicherlich nicht für Ihre Frage gilt, @JeffE!
Lev Reyzin

Antworten:

5

@ JeffE, hier ist ein Artikel, der die minimalen Gewichtszyklen in einem Diagramm zählt. Soweit ich mich erinnere, war es definitiv inspiriert von Kargers Technik / Ergebnis und es war ein lustiger Beweis. Hoffe das hilft beim lehren.

V Vinay
quelle
In diesem Artikel wird die Anzahl der Mindestgewichtszyklen in einer Grafik nicht gezählt. Stattdessen gibt es eine Grenze für die Anzahl der Zyklen, deren Gewicht höchstens ein konstantes Vielfaches des Gewichts des minimalen Gewichtszyklus ist.
Tyson Williams