Parameterized Approaches to Kemeny Rank Aggregation
Channel: Neeldhara Misra
Date: 2022-03-09

Cross-posted from: https://www.youtube.com/watch?v=BguNtYGjJlM

The Kemeny aggregation method defines a consensus ranking based on a collection of rankings. It relies on the Kendall-tau distance between two rankings, which is defined as the number of pairs that are ranked differently. An optimal ranking in this context is one that minimizes the total distance from each of the rankings in the given collection. In this talk, we survey some early lines of work that approached this problem from a parameterized perspective, and its connections with the Feedback Arc Set problem. We then discuss some recent developments, showcasing the use of structural parameterizations for finding not just one solution, but a diverse set of solutions.