.png){kind=icon}
返回
Approximate Condorcet Partitioning: Solving large-scale rank aggregation problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2023.106164.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Rank aggregation has ubiquitous applications in computer science, operations research, and various other fields. Most attention on this problem has focused on an NP-hard variant known as Kemeny aggregation, for which solution approaches with provable guarantees that can handle difficult high-dimensional instances remain elusive. This work introduces exact and approximate methodologies inspired by the social choice foundations of the problem, namely the Condorcet Criterion. We formalize the concept of the finest-Condorcet partition for rankings that may contain ties and specify its required conditions. We prove that this partition is unique and devise an efficient algorithm to obtain it. To deal with instances where it does not yield many subsets, we propose Approximate Condorcet Partitioning (ACP), with which larger subsets can be further broken down and more easily solved. ACP is a scalable solution technique capable of handling large instances while still providing provable guarantees. Although ACP approximation factors are instance-specific, their values were lower than those offered by all known constant-factor approximation schemes - inexact algorithms whose resulting objective values are guaranteed to be within a specified fixed percent of the optimal objective value - for all 113 instances tested herein (containing up to 2,820 items). What is more, ACP obtained solutions that deviated by at most two percent from the optimal objective function values for a large majority of these instances.
Keyword:
Group decision-making
Rank aggregation
Computational social choice
Condorcet criterion
Kemeny-Snell distance
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
Is Rank Aggregation Effective in Recommender Systems? An Experimental Analysis排名聚合在推荐系统中有效吗？实验分析
PREAI
分享收藏
查看更多内容