On the hardness of maximum rank aggregation problems
On the hardness of maximum rank aggregation problems
复制标题
关于最大秩聚合问题的难度
DOI：
10.1016/j.jda.2014.10.002
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Hofmeier
中科院分区：
文献类型：
--
作者：
C. Bachmaier;F.J. Brandenburg;A. Gleißner;A. Hofmeier
排名聚合问题在于根据个人选民的偏好，在一组备选方案上找到一个共识排名。替代品表示的排列，其成对的距离可以用多种方式测量。在这项工作中，我们研究了一系列的距离，包括肯德尔tau，斯皮尔曼footrule，闵可夫斯基，凯莱，汉明，乌拉姆，和相关的编辑距离。与求和的共同中位数不同，我们计算最大值的共识。最大一致性问题是一个最小的封闭球或中心问题，它试图最小化对任何投票者的歧视，我们通过局部置换给出了满足一般要求的所有距离下的最大秩集结问题的NP-困难的一般模式.这统一了一些距离的前NP-硬度结果，并为进一步的结果奠定了基础。特别是，我们建立了一个二分法的秩聚合问题下的斯皮尔曼footrule和Minkowski距离：中值版本是可解的多项式时间，而最大版本是NP-难的。此外，我们表明，最大秩聚合问题是2-逼近下的任何伪度量和固定参数下的肯达尔tau，汉明，闵可夫斯基距离，再次通过修改集的一般模式适用。
The rank aggregation problem consists in finding a consensus ranking on a set of alternatives, based on the preferences of individual voters. The alternatives are expressed by permutations, whose pairwise distance can be measured in many ways.In this work we study a collection of distances, including the Kendall tau, Spearman footrule, Minkowski, Cayley, Hamming, Ulam, and related edit distances. Unlike the common median by summation, we compute the consensus against the maximum. The maximum consensus attempts to minimize the discrimination against any voter and is a smallest enclosing ball or center problem.We provide a general schema via local permutations for theNP-hardness of the maximum rank aggregation problems under all distances which satisfy some general requirements. This unifies formerNP-hardness results for some distances and lays the ground for further ones. In particular, we establish a dichotomy for rank aggregation problems under the Spearman footrule and Minkowski distances: The median version is solvable in polynomial time whereas the maximum version isNP-hard. Moreover, we show that the maximum rank aggregation problem is 2-approximable under any pseudometric and fixed-parameter tractable under the Kendall tau, Hamming, and Minkowski distances, where again a general schema via modification sets applies.
登录
查看更多内容
关于最大等级聚合问题
DOI：
--
发表时间：
2013
期刊：
International Workshop on Combinatorial Algorithms
影响因子：
--
作者：
C. Bachmaier;F. Brandenburg;Andreas Gleißner;A. Hofmeier
通讯作者：
A. Hofmeier
影响因子：
0.8
作者：
T. Biedl;F. Brandenburg;Xiaotie Deng
通讯作者：
Xiaotie Deng
交换和不匹配编辑距离
影响因子：
1.1
作者：
A. Amir;E. Eisenberg;E. Porat
通讯作者：
E. Porat
通过交换和元件重复进行多重基因组重排
影响因子：
1.1
作者：
V. Popov
通讯作者：
V. Popov
具有替换、插入、删除和广义转置的字符串模式识别
影响因子：
8
作者：
B. Oommen;R. Loke
通讯作者：
R. Loke