Rafail Ostrovsky - Publications

Improved algorithms for optimal embeddings.

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai


In the last decade, the notion of metric embeddings with small distortion 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 metric space, given an embedding with small distortion. The better the distortion, the better is the effectiveness of the original algorithm applied to a new metric space.
The goal that was recently studied by Kenyon, Rabani, and Sinclair [Kenyon et al. 2004] is to consider all possible embeddings between two \emph{finite} metric spaces and to find the best possible one, i.e., consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this paper we continue this important direction. In particular, using a theorem of Albert and Atkinson [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 5+2\sqrt{6}. 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 that they cannot find optimal mapping if the optimal distortion is more than 7+4\sqrt{3}. 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.

comment: ACM Transactions on Algorithms 4(4): (2008)

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List