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.