TR06-110 Authors: Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

Publication: 31st August 2006 15:50

Downloads: 2844

Keywords:

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, functional

analysis 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~\cite{krs04} is to consider

all possible embeddings and to try 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, we resolve an open problem stated by the

previous paper, improve their distortion lower bound for the line,

generalize their method and show its inherent limitation. While the improved

distortion differs only by a constant factor for the line (i.e., we show an

improvement from $3+2\sqrt{2}$ to $\our$), it requires novel techniques and

insight into high-distortion patterns. Furthermore, we show an inherent

limitation of this method to be at most $\const$. We also show that previous

techniques on general embeddings apply to a more general class of metrics.