DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

On Greedy Trie Execution

Zbigniew Gołȩbiewski, Filip Zagórski

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 13; 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).

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional