Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00475863
Contributor : Nicolas Nisse <>
Submitted on : Friday, April 23, 2010 - 11:07:38 AM
Last modification on : Wednesday, September 16, 2020 - 12:46:02 PM
Long-term archiving on: : Monday, October 22, 2012 - 3:21:39 PM

File

Menteurs-algotel2010.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00475863, version 1

Citation

Nicolas Hanusse, David Ilcinkas, Adrian Kosowski, Nicolas Nisse. Comment battre la marche aléatoire en comptant ?. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. ⟨inria-00475863⟩

Share

Metrics

Record views

490

Files downloads

151