Abstract
We present a parameterized enumeration algorithm for Kemeny Rank Aggregation, the problem of determining an optimal aggregation, a total order that is at minimum total τ-distance (k t ) from the input multi-set of m total orders (votes) over a set of alternatives (candidates), where the τ-distance between two total orders is the number of pairs of candidates ordered differently. Our \(O^*(4^{k_t\over m})\)-time algorithm constitutes a significant improvement over the previous \(O^*(36^{k_t\over m})\) upper bound.
The analysis of our algorithm relies on the notion of locally-optimal aggregations, total orders whose total τ-distances from the votes do not decrease by any single swap of two candidates adjacent in the ordering. As a consequence of our approach, we provide not only an upper bound of \(4^{k_t\over m}\) on the number of optimal aggregations, but also the first parameterized bound, \(4^{k_t\over m}\), on the number of locally-optimal aggregations, and demonstrate that it is tight. Furthermore, since our results rely on a known relation to Weighted Directed Feedback Arc Set, we obtain new results for this problem along the way.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: Ranking and clustering. J. ACM 55(5), 1–27 (2008)
Alon, N., Lokshtanov, D., Saurabh, S.: Fast fast. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 49–58. Springer, Heidelberg (2009)
Bartholdi, J.J., Tovey, C.A., Trick, M.A.: The computational difficulty of manipulating an election. Social Choice and Welfare 6(3), 227–241 (1989)
Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in computational aspects of voting - a parameterized complexity perspective. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 318–363. Springer, Heidelberg (2012)
Betzler, N., Bredereck, R., Niedermeier, R.: Partial kernelization for rank aggregation: Theory and experiments. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 26–37. Springer, Heidelberg (2010)
Betzler, N., Fellows, M.R., Guo, J., Niedermeier, R., Rosamond, F.A.: Fixed-parameter algorithms for kemeny scores. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 60–71. Springer, Heidelberg (2008)
Betzler, N., Fellows, M.R., Guo, J., Niedermeier, R., Rosamond, F.A.: Fixed-parameter algorithms for Kemeny rankings. Theor. Comput. Sci. 410(45), 4554–4570 (2009)
Biedl, T.C., Brandenburg, F., Deng, X.: On the complexity of crossings in permutations. Discrete Mathematics 309(7), 1813–1823 (2009)
Borda, J.: Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences (1781)
Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5) (2008)
Condorcet, M.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. L’imprimerie royale (1785)
Conitzer, V., Davenport, A., Kalagnanam, J.: Improved bounds for computing Kemeny rankings. In: AAAI 2006: Proc. of the 21st Nat. Conf. on Artificial Intelligence, vol. 1, pp. 620–626 (2006)
Coppersmith, D., Fleischer, L., Rudra, A.: Ordering by weighted number of wins gives a good ranking for weighted tournaments. In: SODA 2006: Proc. of the 17th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 776–782 (2006)
Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: WWW 2001: Proc. of the 10th Int. Conf. on World Wide Web, pp. 613–622 (2001)
Ephrati, E., Rosenschein, J.S.: The Clarke tax as a consensus mechanism among automated agents. In: AAAI 1991: Proc. of the 9th Nat. Conf. on Artificial Intelligence, vol. 1, pp. 173–178 (1991)
Fernau, H., Fomin, F.V., Lokshtanov, D., Mnich, M., Philip, G., Saurabh, S.: Ranking and drawing in subexponential time. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 337–348. Springer, Heidelberg (2011)
Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theor. Comput. Sci. 349(3), 382–391 (2005)
Jackson, B.N., Schnable, P.S., Aluru, S.: Consensus genetic maps as median orders from inconsistent sources. IEEE/ACM Trans. Comput. Biol. Bioinformatics 5(2), 161–171 (2008)
Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol. 6506, pp. 3–14. Springer, Heidelberg (2010)
Kemeny, J.G.: Mathematics without numbers. Daedalus 88, 575–591 (1959)
Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: STOC 2007: Proc. of the 39th Annual ACM Symp. on Theory of Computing, pp. 95–103 (2007)
Simjour, N.: Improved parameterized algorithms for the Kemeny aggregation problem. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 312–323. Springer, Heidelberg (2009)
Van Zuylen, A., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. Mathematics of Operations Research 34(3), 594–620 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nishimura, N., Simjour, N. (2013). Parameterized Enumeration of (Locally-) Optimal Aggregations. In: Dehne, F., Solis-Oba, R., Sack, JR. (eds) Algorithms and Data Structures. WADS 2013. Lecture Notes in Computer Science, vol 8037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40104-6_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-40104-6_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40103-9
Online ISBN: 978-3-642-40104-6
eBook Packages: Computer ScienceComputer Science (R0)