Zbigniew Gołębiewski ; Filip Zagórski
-
On Greedy Trie Execution
dmtcs:3007 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
-
https://doi.org/10.46298/dmtcs.3007
On Greedy Trie ExecutionArticle
Authors: Zbigniew Gołębiewski 1; Filip Zagórski 1
NULL##NULL
Zbigniew Gołębiewski;Filip Zagórski
1 Faculty of Fundamental Problems of Technology [Wroclaw]
In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping <underline>fair</underline> 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 <underline>fair</underline> coin).
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)