On Greedy Trie Execution

Zbigniew Gołębiewski 1 Filip Zagórski 1
1 Faculty of Fundamental Problems of Technology [Wroclaw]
Abstract : In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the question stated in the Prodinger's paper – what happens if not a 0-party is recursively looking for a leader but always a party with a smaller cardinality. We show the lower bound on the number of rounds of the greedy algorithm (for fair coin).
Keywords : Trie leader election
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.377-380, 2012, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01197231
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:51
Dernière modification le : mardi 7 mars 2017 - 15:18:43
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:33:58

Fichier

dmAQ0129.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01197231, version 1

Collections

INSMI | TDS-MACS

Citation

Zbigniew Gołębiewski, Filip Zagórski. On Greedy Trie Execution. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.377-380, 2012, DMTCS Proceedings. 〈hal-01197231〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

182

Téléchargements de fichiers

216

Contact


archive-ouverte@inria.fr