Randomized algorithms for finding a majority element

DOI10.4230/LIPICS.SWAT.2016.9MaRDI QIDQ5369511zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Jukka Suomela, Przemysław Uznański

Publication date 17 October 2017

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

zbMATH Keywords

randomized algorithmslower boundsmajority

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: Given $n$ colored balls, we want to detect if more than $lfloorn/2floor$ of them have the same color, and if so find one ball with such majority color. We are only allowed to choose two balls and compare their colors, and the goal is to minimize the total number of such operations. A well-known exercise is to show how to find such a ball with only $2n$ comparisons while using only a logarithmic number of bits for bookkeeping. The resulting algorithm is called the Boyer--Moore majority vote algorithm. It is known that any deterministic method needs $lceil3n/2ceil-2$ comparisons in the worst case, and this is tight. However, it is not clear what is the required number of comparisons if we allow randomization. We construct a randomized algorithm which always correctly finds a ball of the majority color (or detects that there is none) using, with high probability, only $7n/6+o(n)$ comparisons. We also prove that the expected number of comparisons used by any such randomized method is at least $1.019n$.

Recommendations

• Randomized algorithms for the majority problem
• On randomized algorithms for the majority problem
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• Determining the majority
• Mathematical Foundations of Computer Science 2003

Cited in

(8)

• Algorithmic aspects of majority domination
• Randomized algorithms for the majority problem
• Mathematical Foundations of Computer Science 2003
• The weighted majority algorithm
• Randomized Algorithms for Determining the Majority on Graphs
• On randomized algorithms for the majority problem
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• Majority problems of large query size

This page was built for publication: Randomized algorithms for finding a majority element

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