Search for a majority element

DOI10.1016/S0378-3758(01)00142-2zbMath0994.05002MaRDI QIDQ5957833

Gábor Wiener

Publication date: 10 October 2002

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

zbMATH Keywords

algorithmsbalance beamcounterfeit coinmajority type coinnumber of weighings

Mathematics Subject Classification ID

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

Related Items (19)

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

Cites Work

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

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