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 |