e-space
Manchester Metropolitan University's Research Repository

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

[img]
Preview

Download (612kB) | Preview

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.

Impact and Reach

Statistics

Downloads
Activity Overview
10Downloads
37Hits

Additional statistics for this dataset are available via IRStats2.

Actions (login required)

Edit Item Edit Item