Document Open Access Logo

Randomized Algorithms for Finding a Majority Element

Authors Pawel Gawrychowski, Jukka Suomela, Przemyslaw Uznanski

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.9.pdf
  • Filesize: 467 kB
  • 14 pages

Document Identifiers

Author Details

Pawel Gawrychowski
Jukka Suomela
Przemyslaw Uznanski

Cite As Get BibTex

Pawel Gawrychowski, Jukka Suomela, and Przemyslaw Uznanski. Randomized Algorithms for Finding a Majority Element. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.9

Abstract

Given n colored balls, we want to detect if more than n/2 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 3n/2-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.

Subject Classification

Keywords
  • majority
  • randomized algorithms
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martin Aigner, Gianluca De Marco, and Manuela Montangero. The plurality problem with three colors and more. Theor. Comput. Sci., 337(1-3):319-330, 2005. Google Scholar
  2. Laurent Alonso, Edward M. Reingold, and René Schott. Determining the majority. Inf. Process. Lett., 47(5):253-255, 1993. Google Scholar
  3. Laurent Alonso, Edward M. Reingold, and René Schott. The average-case complexity of determining the majority. SIAM J. Comput., 26(1):1-14, 1997. Google Scholar
  4. Robert S. Boyer and J. Strother Moore. MJRTY: A fast majority vote algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe, pages 105-118, 1991. Google Scholar
  5. Demetres Christofides. On randomized algorithms for the majority problem. Discrete Applied Mathematics, 157(7):1481-1485, 2009. Google Scholar
  6. Fan R. K. Chung, Ronald L. Graham, Jia Mao, and Andrew Chi-Chih Yao. Oblivious and adaptive strategies for the majority and plurality problems. Algorithmica, 48(2):147-157, 2007. Google Scholar
  7. Dorit Dor and Uri Zwick. Selecting the median. SIAM J. Comput., 28(5):1722-1758, 1999. Google Scholar
  8. Dorit Dor and Uri Zwick. Median selection requires (2+ε)n comparisons. SIAM J. Discrete Math., 14(3):312-325, 2001. Google Scholar
  9. David Eppstein and Daniel S. Hirschberg. From discrepancy to majority. In LATIN, volume 9644 of Lecture Notes in Computer Science, pages 390-402. Springer, 2016. Google Scholar
  10. P. Erdős. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc., 51(12):898-902, 12 1945. Google Scholar
  11. M. Fischer and S. Salzberg. Finding a majority among n votes: solution to problem 81-5. Journal of Algorithms, 1982. Google Scholar
  12. Dániel Gerbner, Gyula O. H. Katona, Dömötör Pálvölgyi, and Balázs Patkós. Majority and plurality problems. Discrete Applied Mathematics, 161(6):813-818, 2013. Google Scholar
  13. Daniel Král, Jirí Sgall, and Tomás Tichý. Randomized strategies for the plurality problem. Discrete Applied Mathematics, 156(17):3305-3311, 2008. Google Scholar
  14. Gianluca De Marco and Evangelos Kranakis. Searching for majority with k-tuple queries. Discrete Math., Alg. and Appl., 7(2), 2015. Google Scholar
  15. Gianluca De Marco and Andrzej Pelc. Randomized algorithms for determining the majority on graphs. Combinatorics, Probability & Computing, 15(6):823-834, 2006. Google Scholar
  16. Mike Paterson. Progress in selection. In Algorithm Theory-SWAT'96, pages 368-379. Springer, 1996. Google Scholar
  17. Michael E. Saks and Michael Werman. On computing majority by comparisons. Combinatorica, 11(4):383-387, 1991. Google Scholar
  18. Máté Vizer, Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Balázs Patkós, and Gábor Wiener. Finding a majority ball with majority answers. Electronic Notes in Discrete Mathematics, 49:345-351, 2015. Google Scholar
  19. Gábor Wiener. Search for a majority element. Journal of Statistical Planning and Inference, 100(2):313-318, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact