The plurality problem with three colors and more.

DOI10.1016/J.TCS.2004.12.035zbMath1107.90025OpenAlexW1972715414MaRDI QIDQ557833

Martin Aigner, Manuela Montangero, Gianluca De Marco

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.12.035

zbMATH Keywords

Algorithm analysisCombinatorial searchGameMajority problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Search theory (90B40) Permutations, words, matrices (05A05) Microeconomic theory (price theory and economic markets) (91B24) Combinatorial games (91A46)

Related Items (10)

The majority game with an arbitrary majority ⋮ Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Majority problems of large query size ⋮ Computing majority via multiple queries ⋮ From discrepancy to majority ⋮ How to play the majority game with a liar ⋮ Randomized strategies for the plurality problem ⋮ Finding non-minority balls with majority and plurality queries ⋮ A plurality problem with three colors and query size three ⋮ Searching for majority with k-tuple queries

Cites Work

• Unnamed Item
• Determining the majority
• The worst-case chip problem
• On computing majority by comparisons
• Variants of the majority problem.
• The Average-Case Complexity of Determining the Majority
• STACS 2004
• Mathematical Foundations of Computer Science 2003
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Search for a majority element

This page was built for publication: The plurality problem with three colors and more.