License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.9
URN: urn:nbn:de:0030-drops-60273
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6027/
Go to the corresponding LIPIcs Volume Portal

Gawrychowski, Pawel ; Suomela, Jukka ; Uznanski, Przemyslaw

Randomized Algorithms for Finding a Majority Element

pdf-format:
LIPIcs-SWAT-2016-9.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{gawrychowski_et_al:LIPIcs:2016:6027,
  author =	{Pawel Gawrychowski and Jukka Suomela and Przemyslaw Uznanski},
  title =	{{Randomized Algorithms for Finding a Majority Element}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6027},
  URN =		{urn:nbn:de:0030-drops-60273},
  doi =		{10.4230/LIPIcs.SWAT.2016.9},
  annote =	{Keywords: majority, randomized algorithms, lower bounds}
}

Keywords: majority, randomized algorithms, lower bounds
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI