Search for a majority element

DOI10.1016/S0378-3758(01)00142-2MaRDI QIDQ5957833zbMATH OpenFDO

Authors Gábor Wiener

Publication date 10 October 2002

Published in Journal of Statistical Planning and Inference (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0378-3758(01)00142-2

zbMATH Keywords

algorithmsbalance beamcounterfeit coinmajority type coinnumber of weighings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Determining the majority
• The average complexity of a coin-weighing problem
• Majority and plurality problems
• On computing majority by comparisons
• Adaptive majority problems for restricted query graphs and for weighted sets

Cites work

• Determining the majority
• On computing majority by comparisons
• The Average-Case Complexity of Determining the Majority

Cited in

(22)

• On randomized algorithms for the majority problem
• The worst-case chip problem
• Tight bounds on plurality
• On computing majority by comparisons
• Variants of the majority problem.
• Majority problems of large query size
• From discrepancy to majority
• A plurality problem with three colors and query size three
• Adaptive majority problems for restricted query graphs and for weighted sets
• On more variants of the majority problem
• Truth tellers and liars with fewer questions
• Computing majority via multiple queries
• Searching for a counterfeit coin with two unreliable weighings
• Searching for knights and spies: a majority/minority game
• The majority game with an arbitrary majority
• Finding a majority ball with majority answers
• The average complexity of a coin-weighing problem
• Finding a non-minority ball with majority answers
• The plurality problem with three colors and more.
• Adaptive majority problems for restricted query graphs and for weighted sets
• Computing majority with triple queries
• How to play the majority game with a liar

This page was built for publication: Search for a majority element

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