Given once, 2022
Parameterized Approaches to Kemeny Rank Aggregation
Merging a lot of rankings into one (and finding many good answers) through parameters
An intermediate seminar, for graduate students and up.
Abstract
As published by IISc, February 2022The 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. Most of this talk will be based on the paper Diversity in Kemeny Rank Aggregation: A Parameterized Approach, by Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf (IJCAI 2021).
Source: web.archive.org.