Probabilistic strategies for the partition and plurality problems

DVORAK, Z; V JELINEK; Daniel KRÁĽ; J KYNCL a M SAKS. Probabilistic strategies for the partition and plurality problems. RANDOM STRUCTURES & ALGORITHMS. HOBOKEN: WILEY, 2007, roč. 30, 1-2, s. 63-77. ISSN 1042-9832. Dostupné z: https://doi.org/10.1002/rsa.20148.

Základní údaje

Originální název

Probabilistic strategies for the partition and plurality problems

Autoři

DVORAK, Z; V JELINEK; Daniel KRÁĽ; J KYNCL a M SAKS

Vydání

RANDOM STRUCTURES & ALGORITHMS, HOBOKEN, WILEY, 2007, 1042-9832

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 1.043

DOI

https://doi.org/10.1002/rsa.20148

UT WoS

000243477700005

---

Anotace

V originále

We consider a game played by two players, Paul and Carol. Carol fixes a coloring of it balls with three colors. At each step, Paul chooses a pair of balls and asks Carol whether the balls have the same color. Carol truthfully answers yes or no. In the Plurality problem, Paul wants to find a ball with the most common color. In the Partition problem, Paul wants to partition the balls according to their colors. Paul's goal is to ask Carol the fewest number of questions to reach his goal. We find optimal probabilistic strategies for the Partition problem and the Plurality problem in the considered setting. (c) 2006 Wiley Periodicals, Inc.