Rate-Distortion for Ranking with Incomplete Information
Abstract
We study the rate-distortion relationship in the set of permutations endowed
with the Kendall Tau metric and the Chebyshev metric. Our study is motivated by
the application of permutation rate-distortion to the average-case and
worst-case analysis of algorithms for ranking with incomplete information and
approximate sorting algorithms. For the Kendall Tau 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.