CaltechAUTHORS
  A Caltech Library Service

Rate-Distortion for Ranking with Incomplete Information

Farnoud, Farzad and Schwartz, Moshe and Bruck, Jehoshua (2014) Rate-Distortion for Ranking with Incomplete Information. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20140127-104737329

[img]
Preview
PDF - Accepted Version
See Usage Policy.

208Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140127-104737329

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 analysis of algorithms for ranking with incomplete information and approximate sorting algorithms. For the Kendall t-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.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr125.pdfAuthorTechnical Report
http://arxiv.org/abs/1401.3093arXivDiscussion Paper
Group:Parallel and Distributed Systems Group
Other Numbering System:
Other Numbering System NameOther Numbering System ID
ParadiseETR125
Record Number:CaltechAUTHORS:20140127-104737329
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140127-104737329
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:43524
Collection:CaltechPARADISE
Deposited By: Kristin Buxton
Deposited On:28 Jan 2014 21:43
Last Modified:19 Jan 2016 23:44

Repository Staff Only: item control page