Robert Bredereck

  1. Fixed-Parameter Algorithms for Computing Kemeny Scores - Theory and Practice.

    Authors: Robert Bredereck
    Subjects: Data Structures and Algorithms
    Abstract

    The central problem in this work is to compute a ranking of a set of elements
    which is "closest to" a given set of input rankings of the elements. We define
    "closest to" in an established way as having the minimum sum of Kendall-Tau
    distances to each input ranking. Unfortunately, the resulting problem Kemeny
    consensus is NP-hard for instances with n input rankings, n being an even
    integer greater than three. Nevertheless this problem plays a central role in
    many rank aggregation problems.

Syndicate content