Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2014 | public
Book Section - Chapter

Bounds for Permutation Rate-Distortion

Abstract

We study the rate-distortion relationship in the set of permutations endowed with the Kendall t-metric and the Chebyshev metric. Our study 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 τ-metric we provide bounds for small, medium, and large distortion regimes, while for the Chebyshev metric we present bounds that are valid for all distortions and are especially accurate for small distortions. In addition, for the Chebyshev metric, we provide a construction for covering codes.

Additional Information

© 2014 IEEE. This work was supported in part by an NSF grant CIF-1218005, and a U.S.-Israel Binational Science Foundation (BSF) grant 2010075.

Additional details

Created:
August 20, 2023
Modified:
October 20, 2023