Approximate Sorting

• Autorzy: Giesen J. , Schuberth E. , Stojaković M.
• Języki publikacji: EN

Abstrakty

EN

We show that any comparison based, randomized algorithm to approximate any given ranking of n items within expected Spearman’s footrule distance n²/ν(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 metri

Słowa kluczowe

EN

algorithms; sorting; ranking; Spearman's footrule metric; Kendall's tau metric

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 90, nr 1-2
• Strony: 67--72
• Opis fizyczny: bibliogr. 8 poz.

Twórcy

autor

Giesen J.

autor

Schuberth E.

autor

Stojaković M.

• Department of Mathematics and Informatics University of Novi Sad, Serbia,

Bibliografia

• [1] Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., Tarjan, R. E.: Linear time bounds for median computations, STOC -72: Proceedings of the fourth annual ACM symposium on Theory of computing, ACM Press, 1972.
• [2] Cormen, T. H., Leiserson, C. E., Rivest, R. L.: Introduction to Algorithms, 2nd ed., The MIT Press/McGraw-Hill, 2001.
• [3] Diaconis, P., Graham, R. L.: Spearman-s Footrule as a Measure of Disarray, Journal of the Royal Statistical Society, 39(2), 1977, 262-268.
• [4] Hwang, H. K., Yang, B. Y., Yeh, Y. N.: Presorting algorithms: an average-case point of view, Theoretical Computer Science, 242(1-2), 2000, 29-40.
• [5] Kahn, J., Kim, J. H.: Entropy and Sorting, STOC -92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, ACM Press, 1992.
• [6] Knuth, D. E.: The Art of Computer Programming, vol. 3, AddisonWesley, 1973.
• [7] Mallows, C. L.: Non-null ranking models, Biometrica, 44, 1957, 114-130.
• [8] Yao, A. C.: Probabilistic computations: Towards a unified measure of complexity, FOCS-77: Proceedings of 18th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1977.