Affiliations: Max Plank Institute for Computer Science,
Saarbrücken, Germany. jgiesen@mpi-inf.mpg.de | Institute for Theoretical Computer Science, ETH
Zurich, Switzerland. eva.schuberth@inf.ethz.ch | Department of Mathematics and Informatics, University
of Novi Sad, Serbia. smilos@inf.ethz.ch
Note: [] Address for correspondence: Department of Mathematics and
Informatics, University of Novi Sad, Serbia
Abstract: We show that any comparison based, randomized algorithm to
approximate any given ranking of n items within expected Spearman's footrule
distance n^{2}/ν(n) needs at least n (min{log ν(n), log n} − 6) comparisons in the worst case. This bound is tight up to a constant
factor since there exists a deterministic algorithm that shows that 6n log (n)
comparisons are always sufficient.
Keywords: algorithms, sorting, ranking, Spearman's footrule metric, Kendall's tau metric
