@article{chandran2008improved,
author = {Chandran, Nishanth and Moriarty, Ryan and Ostrovsky, Rafail and Pandey, Omkant and Safari, Mohammad Ali and Sahai, Amit},
title = {Improved algorithms for optimal embeddings},
year = {2008},
month = {August},
abstract = {In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum Lipschitz and bi-Lipschitz constants. One reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. The better distortion, the better the effectiveness of the original algorithm applied to a new metric space.

The goal recently studied by Kenyon et al. [2004] is to consider all possible embeddings between two finite metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this article we continue this important direction. In particular, using a theorem of Albert and Atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. This improves the previous bound of 3 + 2&sqrt;2, solving an open question posed by Kenyon et al. [2004]. Further, we show an inherent limitation of algorithms using the “forbidden pattern” based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4&sqrt;3 (≃ 13.928). Thus, our results are almost optimal for this method. We also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.},
publisher = {ACM - Association for Computing Machinery},
url = {http://approjects.co.za/?big=en-us/research/publication/improved-algorithms-for-optimal-embeddings/},
journal = {ACM Transactions on Algorithms},
volume = {4},
edition = {ACM Transactions on Algorithms},
}