The plurality problem is a game between two participants: Paul and Carole. We are given n balls, each of them is colored with one out of c colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions L, (n) does Paul have to ask in the worst case? For c = 2, the problem is equivalent to the well-known majority problem which has already been solved (Combinatorica 11 (1991) 383-387). In this paper we show that 3 [n/2]-2 <= L-3 (n) <= [5n/3]-2. Moreover, for any c <= n, we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal.

The plurality problem with three colors and more / M., Aigner; G., DE MARCO; Montangero, Manuela. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 337(2005), pp. 319-330. [10.1016/j.tcs.2004.12.035]

The plurality problem with three colors and more

MONTANGERO, Manuela
2005

Abstract

The plurality problem is a game between two participants: Paul and Carole. We are given n balls, each of them is colored with one out of c colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions L, (n) does Paul have to ask in the worst case? For c = 2, the problem is equivalent to the well-known majority problem which has already been solved (Combinatorica 11 (1991) 383-387). In this paper we show that 3 [n/2]-2 <= L-3 (n) <= [5n/3]-2. Moreover, for any c <= n, we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal.
337
319
330
The plurality problem with three colors and more / M., Aigner; G., DE MARCO; Montangero, Manuela. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 337(2005), pp. 319-330. [10.1016/j.tcs.2004.12.035]
M., Aigner; G., DE MARCO; Montangero, Manuela
File in questo prodotto:
File Dimensione Formato  
plurality_journal.pdf

non disponibili

Tipologia: Pre-print dell'autore (bozza pre referaggio)
Dimensione 148.06 kB
Formato Adobe PDF
148.06 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/305208
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 16
social impact