Comment battre la marche aléatoire en comptant ?

Nicolas Hanusse 1, 2 David Ilcinkas 1, 2 Adrian Kosowski 1, 2, 3 Nicolas Nisse 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Nous étudions le problème consistant à trouver une destination t dans un réseau, non fiable, grâce à un agent mobile. Chaque noeud du réseau peut donner un conseil quant au prochain sommet à visiter pour se rapprocher de t. Malheureusement, k noeuds, appelés menteurs, donnent de mauvais conseils. Il est connu que pour un graphe G de n sommets et de degré maximum Delta >= 3, atteindre une cible à distance d de la position initiale peut demander un temps moyen de 2^{Omega(min{d,k})}, pour tout d,k=O(log n), même lorsque G est un arbre. Ce papier étudie une stratégie, appelée R/A, utilisant un compteur (d'étapes) pour alterner entre les phases aléatoires (R) où l'agent choisit aléatoirement une arête incidente, et celles (A) où l'agent suit le conseil local. Aucune connaissance des paramètres n, d, ou k n'est requise, et l'agent n'a pas besoin de se rappeler par quel lien il est entré dans le sommet qu'il occupe. Nous étudions les performances de cette stratégie pour deux classes de graphes, extrêmes pour ce qui est de l'expansion: les anneaux et les graphes réguliers aléatoires (une importante classe d' expanders). Pour l'anneau, l'algorithme R/A requiert un temps moyen de 2d+k^{Theta(1)} (polynomial en d et k) pour une distribution des menteurs la plus défavorable. A l'opposé, nous montrons que dans un anneau, une marche aléatoire biaisée requiert un temps moyen exponentiel en d et k. Pour les graphes aléatoires réguliers, le temps de recherche moyen de l'algorithme R/A est O(k^3 log^3 n) a.a.s.\ Le terme polylogarithmique de cette borne ne peut pas être amélioré, puisque nous montrons une borne inférieure de Omega(log n) pour d,k=Omega(log log n) dans les graphes aléatoires réguliers a.a.s. qui s'applique même lorsque l'agent a le sens de l'orientation.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010
Liste complète des métadonnées


https://hal.inria.fr/inria-00475863
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 23 avril 2010 - 11:07:38
Dernière modification le : vendredi 11 septembre 2015 - 01:06:44
Document(s) archivé(s) le : lundi 22 octobre 2012 - 15:21:39

Fichier

Menteurs-algotel2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00475863, version 1

Collections

Citation

Nicolas Hanusse, David Ilcinkas, Adrian Kosowski, Nicolas Nisse. Comment battre la marche aléatoire en comptant ?. Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010. <inria-00475863>

Partager

Métriques

Consultations de
la notice

306

Téléchargements du document

103