Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner
针对Kemeny排序聚合的NP难问题，提出两种精确算法，其中最优算法可在14个备选方案内合理时间内求解，显著缩短执行时间，并提供了排序数据集及影响执行时间的投票特征分析。
The ranking aggregation problem is gaining attention in different application fields due to its connection with decision making. One of the most famous ranking aggregation methods can be traced back to Kemeny in 1959. Unfortunately, the problem of determining the result of the aggregation proposed by Kemeny, known as Kemeny ranking as it minimizes the number of pairwise discrepancies from a set of rankings given by voters, has been proved to be NP-hard, which unfortunately prevents practitioners from using this method in most real-life problems. In this work, we introduce two exact algorithms for determining the Kemeny ranking. The best of these algorithms guarantees a reasonable search time up to 14 alternatives, showing an important reduction of the execution time in comparison to other algorithms found in the literature. Moreover, a dataset of profiles of rankings is provided and a study of additional aspects of the votes that may have impact on the execution time required to determine the winning ranking is also detailed.