Ranking chain sum orders

Autor: Franz J. Brandenburg, Andreas Gleißner
Rok vydání: 2016
Předmět:
Zdroj: Theoretical Computer Science. 636:66-76
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2016.05.026
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: