0027511 - MÚ 2006 RIV CZ eng V - Research Report
Král´, D. - Tichý, Tomáš - Sgall, Jiří
KAM-DIMATIA Series 2005-722 and ITI Series 2005-238.
[Katedra aplikované matematiky-Diskrétní matematika a teoretická informatika Serie 2005-722 a Institut teoretické informatiky Serie 2005-238.]
Praha: Charles University, 2005. 16 s.
R&D Projects: GA ČR(CZ) GA201/05/0124; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : concrete complexity * randomized algorithms
Subject RIV: BA - General Mathematics

We give asymptotically tight bounds both for randomized algorithms for the plurality problem in the case of two colors and many colors. For the balls colored by $k$ colors, we prove a lower bound $/Omega(kn)$ on the expected number of questions.

Článek studuje pravděpodobnostní strategie pro problém plurality.
Permanent Link: http://hdl.handle.net/11104/0117608