Show simple item record

dc.contributor.author
Gawrychowski, Pawel
dc.contributor.author
Suomela, Jukka
dc.contributor.author
Uznanski, Przemyslaw
dc.contributor.editor
Pagh, Rasmus
dc.date.accessioned
2019-10-17T13:58:05Z
dc.date.available
2017-06-12T03:17:20Z
dc.date.available
2019-10-17T13:58:05Z
dc.date.issued
2016
dc.identifier.isbn
978-3-95977-011-8
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.SWAT.2016.9
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/114561
dc.identifier.doi
10.3929/ethz-b-000114561
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Majority
en_US
dc.subject
Randomized algorithms
en_US
dc.subject
Lower bounds
en_US
dc.subject
Majority
en_US
dc.subject
randomized algorithms
en_US
dc.subject
lower bounds
en_US
dc.title
Randomized algorithms for finding a majority element
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
53
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
9
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
en_US
ethz.event.location
Reykjavik, Iceland
en_US
ethz.event.date
June 22-24, 2016
en_US
ethz.identifier.scopus
ethz.identifier.nebis
010197674
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
ethz.date.deposited
2017-06-12T03:21:20Z
ethz.source
ECIT
ethz.identifier.importid
imp593654413f73f75270
ethz.ecitpid
pub:176353
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-13T16:40:58Z
ethz.rosetta.lastUpdated
2024-02-02T09:37:07Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Randomized%20algorithms%20for%20finding%20a%20majority%20element&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2016&rft.volume=53&rft.spage=9&rft.issn=1868-8969&rft.au=Gawrychowski,%20Pawel&Suomela,%20Jukka&Uznanski,%20Przemyslaw&rft.isbn=978-3-95977-011-8&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.SWAT.2016.9&rft.btitle=15th%20Scandinavian%20Symposium%20and%20Workshops%20on%20Algorithm%20Theory%20(SWAT%202016)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record