Algorithmes aléatoires efficaces et simples où le déterminisme est difficile

J'entends souvent dire que pour de nombreux problèmes, nous connaissons des algorithmes randomisés très élégants, mais pas, ou seulement des solutions déterministes plus compliquées. Cependant, je n'en connais que quelques exemples. Plus en évidence

• Tri rapide randomisé (et algorithmes géométriques associés, par exemple pour les coques convexes)
• Mincut aléatoire
• Test d'identité polynomiale
• Problème de mesure de Klee

Parmi ceux-ci, seuls les tests d'identité polynomiale semblent être vraiment difficiles sans l'utilisation de l'aléatoire.

Connaissez-vous plus d'exemples de problèmes où une solution randomisée est très élégante ou très efficace, mais pas les solutions déterministes? Idéalement, les problèmes devraient être faciles à motiver pour les profanes (contrairement, par exemple, aux tests d'identité polynomiale).

Tri des écrous et boulons

Le problème suivant a été suggéré par Rawlins en 1992: Supposons que l'on vous donne une collection de n écrous et n boulons. Chaque boulon s'adapte exactement à un écrou, et sinon, les écrous et boulons ont des tailles distinctes. Les tailles sont trop proches pour permettre une comparaison directe entre des paires de boulons ou des paires d'écrous. Cependant, vous pouvez comparer n'importe quel écrou à n'importe quel boulon en essayant de les visser ensemble; en temps constant, vous découvrirez si le boulon est trop grand, trop petit ou juste pour l'écrou. Votre tâche consiste à découvrir quel boulon correspond à chaque écrou, ou de manière équivalente, pour trier les écrous et boulons par taille.

Une variante simple du tri rapide randomisé résout le problème en temps avec une forte probabilité. Choisissez un boulon aléatoire; utilisez-le pour partitionner les noix; utilisez l'écrou correspondant pour séparer les boulons; et recurse. Cependant, trouver un algorithme déterministe qui s'exécute même en o ( n 2 ) n'est pas trivial. Des algorithmes déterministes de temps O ( n log n ) ont finalement été trouvés en 1995 par Bradford et indépendamment par Komlós, Ma et Szemerédi. Sous le capot, les deux algorithmes utilisent des variantes du réseau de tri parallèle AKS, donc la constante cachée dans le O ( $O(n \log n)$$o(n^2)$$O(n\log n)$ limité dans le temps est assez grand; la constante cachée pour l'algorithme randomisé est 4.$O(n\log n)$

• Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar et Rafail Ostrovsky. Écrous et boulons assortis. Proc. 5e Ann. ACM-SIAM Symp. Algorithmes discrets , 690–696, 1994.
• Noga Alon, Phillip G. Bradford et Rudolf Fleischer. Assortiment des écrous et boulons plus rapidement. Informer. Proc. Lett. 59 (3): 123-127, 1996.
• Phillip G. Bradford. Écrous et boulons assortis de manière optimale. Technologie. Rep. 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 et Rudolf Fleischer. Assortiment des écrous et boulons plus rapidement. Proc. 6e. Int. Symp. Calcul d'algorithmes. , 402–408, 1995. Lecture Notes Comput. Sci. 1004.
• János Komlós, Yuan Ma et Endre Szemerédi. Écrous et boulons assortis en temps . SIAM J. Discrete Math. 11 (3): 347–372, 1998.$O(n\log n)$
• Gregory J. E. Rawlins. Comparé à quoi? : Une introduction à l'analyse des algorithmes . Computer Science Press / WH Freeman, 1992.

Une fois que vous ne parlez pas seulement de poly-temps mais regardez plutôt les nombreux modèles de calcul que nous étudions, il y en a partout:

Dans Logspace: connectivité ST non dirigée (en RL depuis 1979 et en L uniquement depuis 2005)

En NC: Trouver une correspondance parfaite dans un graphe bipartite en parallèle (en RNC et pas encore connu en NC)

Dans les preuves interactives: les preuves déterministes donnent NP, tandis que les preuves aléatoires peuvent faire PSPACE. Connexes: la vérification d'une preuve de manière déterministe nécessite de regarder toutes les preuves, tandis que les preuves PCP vous permettent de vérifier uniquement un nombre constant de bits.

Dans la conception de mécanismes algorithmiques: de nombreux mécanismes d'approximation véridiques randomisés sans contrepartie déterministe.

En complexité de la communication: la fonction d'égalité nécessite une communication linéaire de manière déterministe mais logarithmique (ou, selon le modèle exact, constante) de façon aléatoire.

Dans les arbres de décision: l'évaluation d'un arbre et-ou nécessite des requêtes linéaires de manière déterministe mais beaucoup moins avec la randomisation. Ceci est essentiellement équivalent à un élagage alpha-bêta qui donne un algorithme sub-linéaire aléatoire pour l'évaluation de l'arbre de jeu.

Dans les modèles de streaming, les modèles informatiques distribués: voir les réponses précédentes.

La plupart des algorithmes de streaming

Dans le modèle de calcul en continu ( AMS , livre ), un algorithme traite une séquence de mises à jour en ligne et est limité pour ne garder qu'un espace sublinéaire. À tout moment, l'algorithme doit pouvoir répondre à une requête.

$t$$i_t \in [n]$$D_m = |\{i_t: t = 1\ldots m\}|$$m$$\Omega(n)$$O(\log n)$$O(\frac{1}{\epsilon^2} + \log n)$$1\pm \epsilon$

$n$$\Delta$$\min(\Omega(\log\Delta),\Omega(\sqrt{\log n}))$

$u$

1. $u$$1/d_u$$d_u>0$$u$$d_u=0$$u$
2. $u$$u$
3. $v$

$O(\log n)$$O(n^{1/\sqrt{\log n}})$

[1] Michael Luby: un algorithme parallèle simple pour le problème des ensembles indépendants maximaux. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074

[2] Alessandro Panconesi, Aravind Srinivasan: Sur la complexité de la décomposition du réseau distribué. J. Algorithms 20 (2): 356-374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017

[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Calcul local: limites inférieure et supérieure. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

Élection des dirigeants dans un cycle de processus anonyme

$1$

Il existe un argument simple (par exemple [1]) selon lequel il n'existe pas d' algorithme d'élection de leader déterministe pour un anneau anonyme.

Modèle: Nous supposons que le calcul avance en tours synchrones où, à chaque tour, chaque processus effectue un calcul local, envoie des messages à ses voisins dans l'anneau et reçoit des messages de ses voisins.

$A$$r\ge 0$$1$

$r\ge 0$$r$$A$$r$$r$$r+1$$A$

$A$$n$$[1,n^4]$

[1] Dana Angluin: Propriétés locales et globales dans les réseaux de processeurs (Extended Abstract). STOC 1980: 82-93. http://doi.acm.org/10.1145/800141.804655

Problème de majorité dans un modèle de requête.

$n$$i$$j$

$n/2$$O(n)$

$O(n)$

FRK Chung, RL Graham, J. Mao et AC Yao, Stratégies inconscientes et adaptatives pour les problèmes de majorité et de pluralité, Proc. COCOON 2005 , p. 329–338.