Algorithmes randomisés utilisant une pile

J'ai développé une nouvelle technique de dérandomisation qui vise des algorithmes randomisés récursifs (ou) plus généralement des algorithmes randomisés qui utilisent une pile. Malheureusement, je n'ai pas pu trouver d'algorithmes aléatoires naturels pour appliquer mes techniques. Les chaînes de Markov récursives et les grammaires stochastiques sont très proches de ce que je recherche. Existe-t-il d'autres algorithmes randomisés (plus naturels) qui font un usage "essentiel" de la pile? Toute aide est grandement appréciée, car je suis coincée avec cela depuis plus de six mois maintenant.

Pour vous donner plus de contexte, je recherche une liste de problèmes similaires à ceux du papier de SivaKumar . Notez que SivaKumar a utilisé le générateur pseudo-aléatoire de Nisan pour dérandomiser ces problèmes.

Comme le souligne Per Vognsen, et plus généralement également, il existe de nombreux algorithmes géométriques qui fonctionnent comme suit: Choisissez un échantillon aléatoire et exécutez récursivement sur l'échantillon et sur d'autres structures dérivées de celui-ci. L'algorithme randomisé de Clarkson pour la programmation linéaire, ainsi que celui de Seidel, et en fait la série Matousek-Sharir-Welzl que Per mentionne, fonctionnent tous de cette manière, et le paradigme de Clarkson s'étend à d'autres situations où vous construisez une sorte de découpe ou epsilon-net et recurse .

Malheureusement, il est peu probable que vous obteniez un nouveau résultat, car il existe des dérandomisations optimales de ces algorithmes, en raison des travaux de Matousek et Chazelle. L'article de Chazelle est un bon point de référence pour ce travail et les travaux antérieurs de Matousek. Mais cela pourrait être un bon test de votre méthode: il était difficile de trouver ces dérandomisations, et si votre méthode fournit une approche de boîte noire commençant par l'algorithme randomisé (plus facile), ce serait bien.

ps c'est probablement l'exemple le plus ennuyeux possible, mais votre méthode fonctionne-t-elle sur le tri rapide ou l'une des méthodes de recherche médiane randomisée?

Que diriez-vous de l'algorithme randomisé de Welzl pour les ellipsoïdes enveloppants minimaux? Il a une profondeur de récursion O (d) où d est la dimension de l'espace.

Je ne sais presque rien de la dérandomisation, donc ce n'est peut-être pas ce que vous cherchez. Si mon exemple ne se qualifie pas (peut-être d'après votre définition, il ne fait qu'un usage inessentiel de la récursivité?), Peut-être pourriez-vous expliquer pourquoi. Cela augmenterait les chances de réponses de meilleure qualité et plus pertinentes des autres.

La version plus rapide de l'algorithme min-cut est en effet très récursive. Voir la figure 2.5 ici , ou tout autre manuel d'algorithmes randomisés standard.