A note on generalized rank aggregation

In the classic rank aggregation (RA) problem, we are given L input lists with potentially inconsistent orders of n elements: Our goal is to find a single order of all elements that minimizes the total number of disagreements with the given orders. The problem is well known to be NP-hard, already for L = 4. We consider a generalization of RA, where each list is associated with a set of orderings, and our goal is to choose one ordering per list and to find a permutation of the elements that minimizes the total disagreements with the chosen orderings. For the case in which the lists completely overlap, i.e. each list contains all n elements, we show that a simple Greedy algorithm yields a (2 - 2/L)-approximation for generalized RA. The case in which the lists only partially overlap, i.e. each list contains a subset of the n elements, is much harder to approximate. In fact, we show that RA with multiple orderings per list and partial overlaps cannot be approximated within any bounded ratio. (C) 2009 Elsevier B.V. All rights reserved.