Name
Abstract | ||
|---|---|---|
Consider a bin containing n balls colored with two colors. In a k-query, k balls are selected by a questioner and the oracle’s reply is related (depending on the computation model being considered)
to the distribution of colors of the balls in this k-tuple; however, the oracle never reveals the colors of the individual balls. Following a number of queries the questioner
is said to determine the majority color if it can output a ball of the majority color if it exists, and can prove that there
is no majority if it does not exist. We investigate two computation models (depending on the type of replies being allowed).
We give algorithms to compute the minimum number of 3-queries which are needed so that the questioner can determine the majority
color and provide tight and almost tight upper and lower bounds on the number of queries needed in each case.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-22685-4_52 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
n ball,pairing model,colors,majority color,minimum number,computing majority,lower bound,balls,individual ball,k ball,search,queries,computation model,y/n model.,triple query,computation models | Journal | 461 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.39 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gianluca De Marco | 1 | 222 | 20.00 |
| Evangelos Kranakis | 2 | 3107 | 354.48 |
| Gábor Wiener | 3 | 64 | 10.65 |