CaltechAUTHORS
  A Caltech Library Service

Bounds for Permutation Rate-Distortion

Farnoud, Farzad and Schwartz, Moshe and Bruck, Jehoshua (2014) Bounds for Permutation Rate-Distortion. In: 2014 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 6-10. ISBN 978-1-4799-5186-4. http://resolver.caltech.edu/CaltechAUTHORS:20150227-075642886

Full text is not posted in this repository. Consult Related URLs below.

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

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ISIT.2014.6874784 DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6874784PublisherArticle
http://resolver.caltech.edu/CaltechAUTHORS:20160119-151223798Related ItemJournal Article
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.
Funders:
Funding AgencyGrant Number
NSFCIF-1218005
Binational Science Foundation (USA-Israel)2010075
Record Number:CaltechAUTHORS:20150227-075642886
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150227-075642886
Official Citation:Farnoud, F.; Schwartz, M.; Bruck, J., "Bounds for permutation rate-distortion," Information Theory (ISIT), 2014 IEEE International Symposium on , vol., no., pp.6,10, June 29 2014-July 4 2014 doi: 10.1109/ISIT.2014.6874784 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6874784&isnumber=6874773
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55312
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:04 Mar 2015 00:07
Last Modified:19 Jan 2016 23:35

Repository Staff Only: item control page