Number of the records: 1
Randomized Strategies for the Plurality Problem
- 1.0318591 - MÚ 2009 RIV NL eng J - Journal Article
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
R&D Projects: GA ČR GA201/05/0124
Institutional research plan: CEZ:AV0Z10190503
Keywords : concrete complexity * randomized algorithms
Subject RIV: BA - General Mathematics
Impact factor: 0.783, year: 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
Permanent Link: http://hdl.handle.net/11104/0167963
File Download Size Commentary Version Access Sgall1.pdf 1 413.1 KB Publisher’s postprint require
Number of the records: 1