Finding a majority ball with majority answers

DOI10.1016/J.ENDM.2015.06.047MaRDI QIDQ322261zbMATH OpenOpenAlexFDO

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

Publication date 14 October 2016

Full work available at URL https://arxiv.org/abs/1509.08276, http://real.mtak.hu/27176/1/Eurocomb15.pdf

zbMATH Keywords

majoritypluralitysearch problems

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(13)

• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• Computing majority with triple queries
• The minimum number of vertices in uniform hypergraphs with given domination number
• Adaptive majority problems for restricted query graphs and for weighted sets
• Majority and plurality problems
• On more variants of the majority problem
• On non-adaptive majority problems of large query size
• Computing majority with triple queries
• Finding a non-minority ball with majority answers
• Majority and plurality problems
• Variants of the majority problem.
• Searching for majority with \(k\)-tuple queries

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)