Parameterized Enumeration of (Locally-) Optimal Aggregations

摘要

We present a parameterized enumeration algorithm for Ke-meny Rank Aggregation, the problem of determining an optimal aggregation, a total order that is at minimum total T-distance (k_t) from the input multi-set of m total orders (votes) over a set of alternatives (candidates), where the T-distance between two total orders is the number of pairs of candidates ordered differently. Our O~* (4~(k_t/m))-time algorithm constitutes a significant improvement over the previous O~* (36~(k_t/m) ) upper bound. The analysis of our algorithm relies on the notion of locally-optimal aggregations, total orders whose total r-distances from the votes do not decrease by any single swap of two candidates adjacent in the ordering. As a consequence of our approach, we provide not only an upper bound of 4~(k_t/m) on the number of optimal aggregations, but also the first pa-rameterized bound, 4~(k_t/m), on the number of locally-optimal aggregations, and demonstrate that it is tight. Furthermore, since our results rely on a known relation to Weighted Directed Feedback Arc Set, we obtain new results for this problem along the way.