Journal article
Bounds for Permutation Rate-Distortion
Abstract
We study the rate-distortion relationship in the set of permutations endowed with the Kendall $\tau $ -metric and the Chebyshev metric (the $\ell _\infty $ -metric). This paper is motivated by the application of permutation rate-distortion to the average-case and worst-case distortion analysis of algorithms for ranking with incomplete information and approximate sorting algorithms. For the Kendall $\tau $ -metric, we provide bounds for various …
Authors
Hassanzadeh FF; Schwartz M; Bruck J
Journal
IEEE Transactions on Information Theory, Vol. 62, No. 2, pp. 703–712
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Publication Date
February 1, 2016
DOI
10.1109/tit.2015.2504521
ISSN
0018-9448