Ich habe eine neue Derandomisierungstechnik entwickelt, die auf rekursive randomisierte Algorithmen (oder allgemeinere randomisierte Algorithmen, die einen Stapel verwenden) abzielt. Leider konnte ich keine natürlichen randomisierten Algorithmen finden, um meine Techniken anzuwenden. Rekursive Markov-Ketten und stochastische Grammatiken kommen dem, was ich suche, sehr nahe. Gibt es andere (natürlichere) randomisierte Algorithmen, die den Stapel "wesentlich" nutzen? Jede Hilfe wird sehr geschätzt, da ich seit mehr als sechs Monaten damit festgefahren bin.
Um Ihnen mehr Kontext zu geben, suche ich nach einer Liste von Problemen, die denen in SivaKumars Artikel ähneln . Beachten Sie, dass SivaKumar Nisans Pseudozufallsgenerator verwendet hat, um diese Probleme zu derandomisieren.
quelle
Antworten:
Wie Per Vognsen und allgemeiner hervorhebt, gibt es viele geometrische Algorithmen, die wie folgt funktionieren: Wählen Sie eine Zufallsstichprobe aus und führen Sie sie rekursiv für die Stichprobe und andere daraus abgeleitete Strukturen aus. Clarksons randomisierter Algorithmus für die lineare Programmierung sowie Seidels und in der Tat die von Per erwähnte Matousek-Sharir-Welzl-Reihe funktionieren alle auf diese Weise, und Clarksons Paradigma erstreckt sich auch auf andere Situationen, in denen Sie eine Art Schnitt oder Epsilon-Netz erstellen und rekursiv arbeiten .
Leider ist es unwahrscheinlich, dass Sie daraus ein neues Ergebnis erhalten, da diese Algorithmen aufgrund der Arbeit von Matousek und Chazelle optimale Derandomisierungen aufweisen. Chazelles Artikel ist ein guter Bezugspunkt für diese Arbeit und frühere Arbeiten von Matousek. Aber es könnte ein guter Test für Ihre Methode sein: Es war schwierig, diese Derandomisierungen zu finden, und wenn Ihre Methode einen Black-Box-Ansatz bietet, der mit dem (einfacheren) randomisierten Algorithmus beginnt, wäre das ordentlich.
ps Dies ist wahrscheinlich das langweiligste Beispiel, aber funktioniert Ihre Methode mit Quicksort oder einer der randomisierten Medianfindungsmethoden?
quelle
Wie wäre es mit Welzls randomisiertem Algorithmus für minimale einschließende Ellipsoide? Es hat die Rekursionstiefe O (d), wobei d die Dimension des Raums ist.
Ich weiß so gut wie nichts über Derandomisierung, daher ist dies möglicherweise nicht das, wonach Sie suchen. Wenn mein Beispiel nicht qualifiziert ist (vielleicht wird Ihrer Definition nach Rekursion nur unwesentlich verwendet?), Könnten Sie vielleicht klarstellen, warum das so ist. Dies würde die Chancen auf qualitativ hochwertigere und sachdienlichere Antworten anderer erhöhen.
quelle
Die schnellere Version des Min-Cut-Algorithmus ist in der Tat sehr rekursiv. Siehe Abbildung 2.5 hier oder ein Standardlehrbuch für randomisierte Algorithmen.
quelle