# Rafail Ostrovsky - Publications

Improved algorithms for optimal embeddings.

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

Abstract:

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

~