Number of the records: 1  

Randomized Strategies for the Plurality Problem

  1. 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

     
    FileDownloadSizeCommentaryVersionAccess
    Sgall1.pdf1413.1 KBPublisher’s postprintrequire
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.