Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation
Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation
复制标题
DOI：
10.1007/s10458-013-9236-y
复制
发表时间：
2014-09
影响因子：
1.9
通讯作者：
Nadja Betzler;Robert Bredereck;R. Niedermeier
中科院分区：
文献类型：
--
作者：
Nadja Betzler;Robert Bredereck;R. Niedermeier
摘要Kemeny秩聚合是一个共识发现问题，在从网络搜索和数据库的经典投票到生物信息学的许多领域都很重要。潜在的决策问题Kemeny分数是NP完全的，即使在四个输入排名的情况下，被聚合成一个“中位数排名”。我们分析了高效的多项式时间数据减少规则，可证明的性能界限，使我们能够找到甚至所有的最佳中位数排名。我们表明，我们减少的实例包含在最候选人，其中d_a da表示输入投票之间的平均肯德尔的tau距离。在理论方面，这将“部分问题核”的相应结果从二次改进为线性大小。在这方面，我们提供了一个常用的数据减少的理论分析。在实践方面，我们提供了基于网络搜索和体育比赛的数据的实验结果，例如，在毫秒内计算超过100个候选人的真实世界实例的最佳中位数排名。此外，我们进行实验与随机生成的数据的基础上两个随机分布模型的排列。
Abstract Kemeny Rank Aggregation is a consensus finding problem important in many areas ranging from classical voting over web search and databases to bioinformatics. The underlying decision problem Kemeny Score is NP-complete even in case of four input rankings to be aggregated into a “median ranking”. We analyze efficient polynomial-time data reduction rules with provable performance bounds that allow us to find even all optimal median rankings. We show that our reduced instances contain at most candidates where d_a da denotes the average Kendall’s tau distance between the input votes. On the theoretical side, this improves a corresponding result for a “partial problem kernel” from quadratic to linear size. In this context we provide a theoretical analysis of a commonly used data reduction. On the practical side, we provide experimental results with data based on web search and sport competitions, eg, computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds. Moreover, we perform experiments with randomly generated data based on two random distribution models for permutations.