×

Ranking chain sum orders. (English) Zbl 1342.68141

Summary: 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 \(\mathcal{NP}\)-complete for a total and a chain sum order of height at least 12. Both problems remain \(\mathcal{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.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ailon, N., Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists, Algorithmica, 57, 2, 284-300 (2010) · Zbl 1184.68627
[2] Alon, N., Ranking tournaments, SIAM J. Discrete Math., 20, 1, 137-142 (2006) · Zbl 1112.05043
[3] Bachmaier, C.; Brandenburg, F. J.; Gleißner, A.; Hofmeier, A., On the hardness of maximum rank aggregation problems, J. Discrete Algorithms, 31, 2-13 (2015) · Zbl 1322.68086
[4] Baker, K. A.; Fishburn, P. C.; Roberts, F. S., Partial orders of dimension 2, Networks, 2, 1, 11-28 (1971) · Zbl 0247.06002
[5] Bansal, M. S.; Fernandez-Baca, D., Computing distances between partial rankings, Inform. Process. Lett., 109, 238-241 (2009) · Zbl 1191.68820
[6] Barth, W.; Mutzel, P.; Jünger, M., Simple and efficient bilayer cross counting, J. Graph Algorithms Appl., 8, 2, 179-194 (2004) · Zbl 1088.05502
[7] Bartholdi, J. J.; Tovey, C. A.; Trick, M. A., Voting schemes for which it can be difficult to tell who won the election, Soc. Choice Welf., 6, 2, 157-165 (1989) · Zbl 0672.90004
[8] Bechet, D.; De Groote, P.; Retoré, C., A complete axiomatisation for the inclusion of series-parallel partial orders, (Comon, H., Rewriting Techniques and Applications. Rewriting Techniques and Applications, Lecture Notes in Comput. Sci., vol. 1232 (1997), Springer), 230-240 · Zbl 1379.06001
[9] Betzler, N.; Dorn, B., Towards a dichotomy for the possible winner problem in elections based on scoring rules, J. Comput. System Sci., 76, 8, 812-836 (2010) · Zbl 1232.91168
[10] Betzler, N.; Fellows, M. R.; Guo, J.; Niedermeier, R.; Rosamond, F. A., Fixed-parameter algorithms for Kemeny rankings, Theoret. Comput. Sci., 410, 8, 4554-4570 (2009) · Zbl 1179.91062
[11] Biedl, T.; Brandenburg, F. J.; Deng, X., On the complexity of crossings in permutations, Discrete Math., 309, 7, 1813-1823 (2009) · Zbl 1173.05003
[12] Borda, J.-C., Mémoire aux les élections au scrutin, Histoire de l’Académie Royale des Sciences (1781)
[13] Brandenburg, F. J.; Gleißner, A.; Hofmeier, A., Comparing and aggregating partial orders with Kendall tau distances, Discrete Math. Algorithms Appl., 5, 2 (2013) · Zbl 1294.06002
[14] Brandenburg, F. J.; Gleißner, A.; Hofmeier, A., The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders, J. Comb. Optim., 26, 2, 310-332 (2013) · Zbl 1298.90082
[15] Charbit, P.; Thomassé, S.; Yeo, A., The minimum feedback arc set problem is NP-hard for tournaments, Combin. Probab. Comput., 16, 1, 1-4 (2007) · Zbl 1120.05038
[16] Condorcet, M. J., Éssai sur l’application de l’analyse à la probalité des décisions rendues à la pluralité des voix (1785)
[17] Conitzer, V.; Sandholm, T.; Lang, J., When are elections with few candidates hard to manipulate& quest, J. ACM, 54, 3, 14 (2007) · Zbl 1292.91062
[18] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press · Zbl 1047.68161
[19] Critchlow, D. E., Metric Methods for Analyzing Partially Ranked Data, Lecture Notes in Statist., vol. 34 (1985), Springer · Zbl 0589.62041
[20] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Graph Drawing: Algorithms for the Visualization of Graphs (1999), Prentice Hall · Zbl 1057.68653
[21] Downey, R. G.; Fellows, M. R., Parameterized Complexity, Monogr. Comput. Sci. (1999), Springer · Zbl 0914.68076
[22] Dror, M.; Steiner, G., Strong-weak precedence in scheduling: extensions to series-parallel orders, Discrete Appl. Math., 158, 1767-1776 (2010) · Zbl 1198.90176
[23] Dwork, C.; Kumar, R.; Naor, M.; Sivakumar, D., Rank aggregation methods for the web, (Proc. World Wide Web Conference. Proc. World Wide Web Conference, WWW 2001 (2001)), 613-622
[24] Fagin, R.; Kumar, R.; Mahdian, M.; Sivakumar, D.; Vee, E., Comparing partial rankings, SIAM J. Discrete Math., 20, 3, 628-648 (2006) · Zbl 1121.06002
[25] Fagin, R.; Kumar, R.; Sivakumar, D., Comparing top \(k\) lists, SIAM J. Discrete Math., 17, 1, 134-160 (2003) · Zbl 1057.68075
[26] Knight, W. R., A computer method for calculating Kendall’s tau with ungrouped data, J. Amer. Statist. Assoc., 61, 314, 436-439 (1966) · Zbl 0138.13202
[27] Muñoz, X.; Unger, W.; Vrto, I., One sided crossing minimization is NP-hard for sparse graphs, (Mutzel, P.; Jünger, M.; Leipert, S., Proc. Graph Drawing. Proc. Graph Drawing, Lecture Notes in Comput. Sci., vol. 2265 (2002), Springer), 115-123 · Zbl 1054.68598
[28] Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038
[29] Trotter, W. T., Combinatorics and Partially Ordered Sets (1992), The John Hopkins University Press · Zbl 0764.05001
[30] Xia, L.; Conitzer, V., Determining possible and necessary winners given partial orders, J. Artificial Intelligence Res., 41, 25-67 (2011) · Zbl 1218.91040
[31] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. Algebr. Discrete Methods, 3, 3, 351-358 (1982) · Zbl 0516.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.