Abstract
In this paper, we consider algorithmic issues of the rank aggregation problem for information retrieval on the Web. We introduce a weighted version of the metric of the normalized Kendall-τ distance, originally proposed for the problem by Dwork, et al.,7 and show that it satisfies the extended Condorcet criterion. Our main technical contribution is a polynomial time approximation scheme, in addition to a practical heuristic algorithm with ratio 2 for the NP-hard problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arora, A. Frieze and H. Kaplan, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, FOCS96:21–30
S. Arora, D. Karger and M. Karpinski, Polynomial-time approximation schemes for dense instances of NP-hard optimization problems, STOC95:284–293
J.P. Barthelemy, A. Guenoche and O. Hudry, Median linear orders: Heuristics and a branch and bound algorithm, European Journal of Operational Research 42(1989): 313–325.
J.P. Barthelemy and B. Monjardet, The median Procedure in cluster analysis and social choice theory, Mathematical Social Sciences 1(1981): 235–267.
J.J. Bartholdi, D.A. Tovey and M.A. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare, 6(1989): 157–165.
I. Charon, A. Guenoche, O. Hudry and F. Woirgard, New results on the computation of median orders, Discrete Mathematics 165/166(1997): 139–153.
C. Dwork, R. Kumar, M. Naor and D. Sivakumar, Rank aggregation methods for the web, WWW10 (2001), 613–622.
D. Gillman, A Chernoff bound for random walks on expanders, SIAM J. Comput. 27(1998): 1203–1220.
R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller and J.W. Thatcher, eds., Complexity of Computer Computations (Plenue, New York, 1972) 85–103.
J.G. Kemeny, Mathematics without numbers, Daedalus 88(1959): 577–591.
P. Raghavan, Probabilistic construction of deterministic algorithms: Approximating packing integer programs, Journal of Computer and System Sciences 37(1988): 130–143.
P. Raghavan and C. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica 7(1987): 365–374.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Deng, X., Fang, Q., Zhu, S. (2003). Approximate Rank Aggregation. In: Warnow, T., Zhu, B. (eds) Computing and Combinatorics. COCOON 2003. Lecture Notes in Computer Science, vol 2697. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45071-8_28
Download citation
DOI: https://doi.org/10.1007/3-540-45071-8_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40534-4
Online ISBN: 978-3-540-45071-9
eBook Packages: Springer Book Archive