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.