Finding a majority ball with majority answers

DOI10.1016/J.ENDM.2015.06.047zbMATH Open1386.68113arXiv1509.08276OpenAlexW2130922498MaRDI QIDQ322261FDOQ322261

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Balázs Patkós, Máté Vizer, Gábor Wiener

Publication date: 14 October 2016

Abstract: Suppose we are given a set of $n$ balls $b_1,ldots,b_n$ 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 $b_{i_1},b_{i_2},b_{i_3}$. As an answer to such a query we obtain (the index of) a {em 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 {em non-minority ball}, that is, a ball whose color occurs at least $fracn2$ times among the $n$ balls. We show that the minimum number of queries needed to solve this problem is $Theta(n)$ in the adaptive case and $Theta(n^3)$ in the non-adaptive case. We also consider some related problems.

Full work available at URL: https://arxiv.org/abs/1509.08276

Recommendations

• Finding a non-minority ball with majority answers
• Majority and plurality problems
• Majority and plurality problems
• Computing majority with triple queries
• On non-adaptive majority problems of large query size

zbMATH Keywords

majoritypluralitysearch problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Cites Work

• On computing majority by comparisons
• Variants of the majority problem.
• Search for a majority element
• Determining the majority
• Computing majority with triple queries
• The quantum black-box complexity of majority
• Majority and plurality problems
• Probabilistic strategies for the partition and plurality problems
• Density-Based Group Testing
• Searching for majority with k-tuple queries

Cited In (2)

• The minimum number of vertices in uniform hypergraphs with given domination number
• Variants of the majority problem.

This page was built for publication: Finding a majority ball with majority answers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322261)