Finding non-minority balls with majority and plurality queries

DOI10.1016/J.DAM.2020.03.023zbMATH Open1442.90094arXiv1812.08850OpenAlexW3011220111MaRDI QIDQ777450FDOQ777450

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)

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$.

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

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

zbMATH Keywords

adaptive algorithmscombinatorial searchmajority and plurality problems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Adaptive majority problems for restricted query graphs and for weighted sets
• Computing majority via multiple queries
• Majority and plurality problems
• A plurality problem with three colors and query size three
• On non-adaptive majority problems of large query size
• Adaptive majority problems for restricted query graphs and for weighted sets
• 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)