Randomized Strategies for the Plurality Problem

0318591 - MÚ 2009 RIV NL eng J - Článek v odborném periodiku
Král´, D. - Tichý, T. - Sgall, Jiří
Randomized Strategies for the Plurality Problem.
[Pravděpodobnostní strategie pro problém plurality.]
Discrete Applied Mathematics. Roč. 156, č. 17 (2008), s. 3305-3311. ISSN 0166-218X. E-ISSN 1872-6771
Grant CEP: GA ČR GA201/05/0124
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: concrete complexity * randomized algorithms
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.783, rok: 2008

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
Trvalý link: http://hdl.handle.net/11104/0167963