Finding non-minority balls with majority and plurality queries

DOI10.1016/J.DAM.2020.03.023MaRDI QIDQ777450zbMATH OpenOpenAlexFDO

Authors Huilan Chang, Dániel Gerbner, Balázs Patkós

Publication date 7 July 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.08850, http://real.mtak.hu/114228/1/1812.08850v1

zbMATH Keywords

adaptive algorithmscombinatorial searchmajority and plurality problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Search theory (90B40)

Abstract: Given a set of $n$ colored balls, a extit{majority, non-minority or plurality ball} is one whose color class has size more than $n/2$, at least $n/2$ or larger than any other color class, respectively. We describe linear time algorithms for finding non-minority balls using query sets of size $q$ of the following form: the answer to a majority/plurality query $Q$ is a majority/plurality ball in $Q$ or the statement that there is no such ball in $Q$.

Recommendations

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

Cites work

• Computing majority via multiple queries
• Computing majority with triple queries
• Finding a non-minority ball with majority answers
• From discrepancy to majority
• Majority and plurality problems
• On computing majority by comparisons
• The plurality problem with three colors and more.
• Variants of the majority problem.

Cited in

(8)

• Adaptive majority problems for restricted query graphs and for weighted sets
• Computing majority via multiple queries
• Adaptive majority problems for restricted query graphs and for weighted sets
• A plurality problem with three colors and query size three
• Majority and plurality problems
• On non-adaptive majority problems of large query size
• Finding a non-minority ball with majority answers
• Majority and plurality problems

This page was built for publication: Finding non-minority balls with majority and plurality queries

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