Revisiting the Majority Problem: Average-Case Analysis with Arbitrarily Many Colours

Kleerekoper, A (2016) Revisiting the Majority Problem: Average-Case Analysis with Arbitrarily Many Colours. ArXiv. ISSN 1868-8969

Preview

Published Version
Available under License Creative Commons Attribution.
Download (612kB) | Preview

Official URL: https://doi.org/10.48550/arXiv.1606.05123

Abstract

The majority problem is a special case of the heavy hitters problem. Whilst the special case of two-colours has been well studied, the average-case performance for arbitrarily many colours has not. In this paper we present an analysis of the average-case performance of the three deterministic algorithms that appear in the literature. For each, we consider straightforward optimisations that, to our knowledge, have not been previously considered.

Item Type:	Article
Peer-reviewed:	No
Date Deposited:	31 Oct 2016 14:35
Publisher:	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Additional Information:	This open access article can be located at https://arxiv.org/, published by Leibniz-Schloss Dagstuhl - Zentrum fuer Informatik.
Divisions:	Faculties > Science and Engineering
Subject terms:	cs.DS, cs.DS, F.2.2, cs.DS, cs.DS, F.2.2
URI:	https://e-space.mmu.ac.uk/id/eprint/322
DOI:	https://doi.org/10.48550/arXiv.1606.05123
ISSN	1868-8969

Impact and Reach

Statistics

DownloadsShow export options

Activity Overview

6 month trend

247Downloads

6 month trend

316Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Repository staff only

Edit record