On computing majority by comparisons

DOI10.1007/BF01275672MaRDI QIDQ1181015zbMATH OpenFDO

Authors Michael Saks, Michael Werman

Publication date 27 June 1992

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01275672

zbMATH Keywords

partition

Mathematics Subject Classification ID

Partitions of sets (05A18) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Review text

The authors investigate the problem of finding an element in the larger part of a partition of an \(n\)-element set into two classes based on comparison, i.e. for any two elements there is a decision whether or not they belong to the same part. They give an algorithm, which finds such an element with at most \(n-B(n)\) comparisons, where \(B(n)\) is the number of 1's in the binary expansion of \(n\), and they show that this algorithm is optimal.

Recommendations

• Determining the majority
• The Average-Case Complexity of Determining the Majority
• Determining the majority: The biased case
• Search for a majority element
• Finding an Approximate Maximum

Cites work

• Finding repeated elements
• scientific article; zbMATH DE number 3460321 (Why is no real title available?)
• On recognizing graph properties from adjacency matrices

Cited in

(35)

• Randomized strategies for the plurality problem
• On randomized algorithms for the majority problem
• The worst-case chip problem
• Tight bounds on plurality
• Determining the majority: The biased case
• Variants of the majority problem.
• Finding modes with equality comparisons
• Majority problems of large query size
• From discrepancy to majority
• New applications of the incompressibility method. II
• A plurality problem with three colors and query size three
• On the decision tree complexity of threshold functions
• 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
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• Computing majority via multiple queries
• Searching for knights and spies: a majority/minority game
• Finding mode using equality comparisons
• The majority game with an arbitrary majority
• Randomized algorithms for the majority problem
• Finding a majority ball with majority answers
• A New Lower Bound for the Set-Partitioning Problem
• The Average-Case Complexity of Determining the Majority
• On non-adaptive majority problems of large query size
• Finding a non-minority ball with majority answers
• Determining majority in networks with local interactions and very small local memory
• Searching for majority with k-tuple queries
• The plurality problem with three colors and more.
• Search for a majority element
• Adaptive majority problems for restricted query graphs and for weighted sets
• Determining the majority
• Computing majority with triple queries
• Finding non-minority balls with majority and plurality queries
• How to play the majority game with a liar

This page was built for publication: On computing majority by comparisons

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