Name
Abstract | ||
|---|---|---|
Suppose we are given a set of n balls {b1,…,bn} each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls {bi1,bi2,bi3}. As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a non-minority ball, that is, a ball whose color occurs at least n2 times among the n balls. We show that the minimum number of queries needed to solve this problem is Θ(n) in the adaptive case and Θ(n3) in the non-adaptive case. We also consider some related problems. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.dam.2016.11.012 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Combinatorial search,Majority,Median | Discrete mathematics,Combinatorics,Ball (bearing),Mathematics | Journal |
Volume | ISSN | Citations |
219 | 0166-218X | 2 |
PageRank | References | Authors |
0.39 | 9 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Gerbner | 1 | 46 | 21.61 |
| Balázs Keszegh | 2 | 156 | 24.36 |
| Dömötör Pálvölgyi | 3 | 202 | 29.14 |
| Balázs Patkós | 4 | 85 | 21.60 |
| Máté Vizer | 5 | 27 | 14.06 |
| Gábor Wiener | 6 | 64 | 10.65 |