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
    Published Version
    Available under License Creative Commons Attribution.

    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

    Activity Overview
    6 month trend
    144Downloads
    6 month trend
    284Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record