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