期刊
JOURNAL OF THE ACM
卷 55, 期 5, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1411509.1411513
关键词
Algorithms; Theory; Rank aggregation; consensus clustering; correlation clustering; minimum feedback arc-set; tournaments
类别
资金
- Princeton University
- National Science Foundation (NSF) ITR [CCR-0205594]
- DOE Early Career Principal Investigator award [FG02-02ER25540]
- NSF CAREER [CCR-0237113]
We address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the extent of disagreement with the respective inputs. Specifically, the problems we address are rank aggregation, the feedback arc set problem on tournaments, and correlation and consensus clustering. We show that for all these problems (and various weighted versions of them), we can obtain improved approximation factors using essentially the same remarkably simple algorithm. Additionally, we almost settle a long-standing conjecture of Bang-Jensen and Thomassen and show that unless NP subset of BPP, there is no polynomial time algorithm for the problem of minimum feedback arc set in tournaments.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据