Approximation algorithms for information dissemination problems.

Pierre Fraigniaud (1) , Sandrine Vial (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Broadcasting and gossiping are known to be NP-hard problems. This paper deals with approximation algorithms for such problems. We consider both round-complexity and step-complexity in the telephone model. After an overview of previously derived approximation algorithms, we present new strategies for broadcasting and gossiping in any graphs. Broadcasting strategies are based on the construction of edge-disjoint spanning trees. Gossiping strategies are based on on-line computation of matchings along with the gossiping process. Our approximation algorithms for broadcasting offer almost optimal complexity when the number of messages to be broadcasted is large. We show that our best approximation algorithm for gossiping performs optimally in many cases. We also show experimentally that it can perform faster than the best known handmade algorithms in some particular cases.

La diffusion et l'échange total sont des problèmes NP-durs. Cet article traite d'algorithmes d'approximation pour ces problèmes. Nous considérons à la fois la complexité en temps et en taille de messages dans le modèle ``téléphone''. Après un bref aperçu des algorithmes d'approximation existants, nous présentons de nouvelles stratégies pour la diffusion et l'échange total dans un graphe quelconque. Les stratégies pour la diffusion sont basées sur la construction d'arbres de recouvrement arêtes-disjoints. Celles pour l'échange total sont basées sur le calcul de couplages tout au long du processus d'échange total. Nos algorithmes d'approximation pour la diffusion ont une complexité presque optimale lorsque le nombre de messages diffusés est grand. Nous montrons que notre meilleur algorithme d'approximation pour l'échange total s'exécute optimalement dans de nombreux cas. Nous montrons, expérimentalement, que cet algorithme peut dans certains cas, produire des algorithmes d'échange total plus rapides que les meilleurs algorithmes connus.

Mots clés: Approximation Algorithms; Broadcasting; Diffusion; Gossiping

Mots clés: Algorithmes d'approximation; Echange total

Domaines: Informatique [cs]

Pierre Fraigniaud, Sandrine Vial. Approximation algorithms for information dissemination problems.. [Research Report] LIP RR-1995-15, Laboratoire de l'informatique du parallélisme. 1995, 2+23p. ⟨hal-02101953⟩