Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1383369.1383376 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
improved algorithm,optimal bijection,possible embeddings,metric embeddings,optimal embeddings,metric space,small distortion,optimal distortion,finite metric space,optimal mapping,better distortion,new metric space,algorithm design,objective function,dynamic programming,metric spaces,discrete mathematics,combinatorial optimization | Journal | 4 |
Issue | ISSN | Citations |
4 | 1549-6325 | 3 |
PageRank | References | Authors |
0.44 | 16 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nishanth Chandran | 1 | 375 | 21.86 |
| Ryan Moriarty | 2 | 45 | 2.97 |
| Rafail Ostrovsky | 3 | 8743 | 588.15 |
| Omkant Pandey | 4 | 2015 | 82.24 |
| Mohammad Ali Safari | 5 | 68 | 6.76 |
| Amit Sahai | 6 | 13566 | 545.52 |