Low-distortion embeddings of general metrics into the line

Abstract

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer science.Most of the known embedding results are "absolute",that is, of the form: any metric Y from a given class of metrics C can be embedded into a metric X with low distortion c. This is beneficial if one can guarantee low distortion for all metrics Y in C. However, in any situations, the worst-case distortion is too large to be meaningful. For example, if X is a line metric, then even very simple metrics (an n - point star or an n -point cycle) are embeddable into X only with distortion linear in n. Nevertheless, embeddings into the line (or into low-dimensional spaces) are important for many applications.A solution to this issue is to consider "relative" (or "approximation") embedding problems, where the goal is to design an (a-approxiation) algorithm which, given any metric X from C as an input, finds an embedding of X into Y which has distortion a *cY (X), where cY (X)is the best possible distortion of an embedding of X into Y.In this paper we show algorithms and hardness results for relative embedding problems.In particular we give: •an algorith that, given a general metric M, finds an embedding with distortion O (Δ3⁄4 poly(c line (M))), where Δ is the spread of M•an algorithm that,given a weighted tree etric M, finds an embedding with distortion poly(c line (M)) •a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor polynomial in n,even for weighted tree metrics with spread Δ=n O (1).