Ranking chain sum orders
Ranking chain sum orders
复制标题
排名链总和订单
DOI：
10.1016/j.tcs.2016.05.026
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Gleißner
中科院分区：
文献类型：
--
作者：
F.J. Brandenburg;A. Gleißner
排名信息是信息科学、互联网搜索、投票系统和体育领域的一个重要课题。在全信息方法中，排名是候选人的总顺序。在最近邻Kendall tau距离下，通过两两比较比较两个排序，研究了距离和排序聚集问题。在许多情况下，信息是不完整的，排序是部分顺序给出的。如果排名允许平局，并将平局的候选人视为同等，则获得桶顺序。这样就可以在几乎线性的时间内有效地解决距离和秩聚集问题。链和顺序与桶顺序互补，由一组不相交的总顺序组成。它的宽度和高度分别是总订单的数量和最大尺寸。我们证明了宽度有界或高度最多为2的总阶和链和阶的距离和秩聚集问题可以在多项式时间内解决，并且对于高度至少为12的总阶和链和阶是np完全的。对于总顺序和堆顺序（即从单淘汰赛（在体育中）获得的偏顺序），这两个问题都是np完全的。然而，对于距离和Ulam距离，问题是固定参数可处理的，但是对于阶维，问题是固定参数难处理的。
Ranking information is an important topic in information sciences, Internet searching, voting systems, and sports. In the full information approach, a ranking is a total order of the candidates. We compare two rankings by pairwise comparisons under the nearest neighbor Kendall tau distance and study the distance and rank aggregation problems. In many settings, the information is incomplete and a ranking is given by a partial order. A bucket order is obtained if a ranking allows ties and treats tied candidates as equivalent. Then the distance and rank aggregation problems can be solved efficiently in almost linear time. A chain sum order is complementary to a bucket order and consists of a set of disjoint total orders. Its width and height is the number and the maximum size of the total orders, respectively. We show that the distance and rank aggregation problems of a total order and a chain sum order of bounded width or of height at most two can be solved in polynomial time and are NP-complete for a total and a chain sum order of height at least 12. Both problems remain NP-complete for a total and a heap order which is the partial order obtained from a single-elimination tournament (in sports). However, the problems are fixed-parameter tractable with respect to the distance and the Ulam distance, but are fixed-parameter intractable with respect to the order dimension.
登录
查看更多内容
计算部分排名之间的距离
影响因子：
0.5
作者：
Mukul S. Bansal;David Fernández
通讯作者：
David Fernández
DOI：
10.1137/0603036
发表时间：
1982-09
期刊：
Siam Journal on Algebraic and Discrete Methods
影响因子：
--
作者：
M. Yannakakis
通讯作者：
M. Yannakakis
影响因子：
0.8
作者：
T. Biedl;F. Brandenburg;Xiaotie Deng
通讯作者：
Xiaotie Deng
部分交换线性逻辑和兰贝克微积分乘积的自然演绎和归一化
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
M. Amblard;Christian Retoré
通讯作者：
Christian Retoré
关于最大秩聚合问题的难度
DOI：
10.1016/j.jda.2014.10.002
发表时间：
2014
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
C. Bachmaier;F.J. Brandenburg;A. Gleißner;A. Hofmeier
通讯作者：
A. Hofmeier