Low-distortion embeddings of general metrics into the line
Low-distortion embeddings of general metrics into the line
复制标题
将一般指标低失真嵌入到线路中
DOI：
10.1145/1060590.1060624
复制
发表时间：
2005
影响因子：
22.7
通讯作者：
Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
Mihai Badoiu;Julia Chuzhoy;P. Indyk;Anastasios Sidiropoulos
两个度量空间之间的低失真嵌入是一种映射，它将每对点之间的距离保持在一个称为失真的小因子范围内。低失真嵌入最近在计算机科学中得到了大量应用。大多数已知的嵌入结果是“绝对的”，即形式为：来自给定度量类\(C\)的任何度量\(Y\)都可以以低失真\(c\)嵌入到度量\(X\)中。如果能够保证\(C\)中所有度量\(Y\)的低失真，这是有益的。然而，在许多情况下，最坏情况下的失真太大以至于没有意义。例如，如果\(X\)是一种线度量，那么即使是非常简单的度量（一个\(n\)点星或一个\(n\)点环）也只能以与\(n\)成线性关系的失真嵌入到\(X\)中。然而，嵌入到直线（或低维空间）对于许多应用是重要的。解决这个问题的一种方法是考虑“相对”（或“近似”）嵌入问题，其目标是设计一种（\(a\) - 近似）算法，该算法在给定来自\(C\)的任何度量\(X\)作为输入时，找到\(X\)到\(Y\)的嵌入，其失真为\(a\times c_Y(X)\)，其中\(c_Y(X)\)是\(X\)嵌入到\(Y\)的最佳可能失真。在本文中，我们展示了相对嵌入问题的算法和困难性结果。特别是我们给出：
• 一种算法，给定一个一般度量\(M\)，找到失真为\(O(\Delta^{\frac{3}{4}}\text{poly}(c_{\text{line}}(M)))\)的嵌入，其中\(\Delta\)是\(M\)的扩展度
• 一种算法，给定一个加权树度量\(M\)，找到失真为\(\text{poly}(c_{\text{line}}(M))\)的嵌入
• 一个困难性结果，表明计算最小线失真在\(n\)的多项式因子内是难以近似的，即使对于扩展度\(\Delta = n^{O(1)}\)的加权树度量也是如此。
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 <i>Y</i> from a given class of metrics <i>C</i> can be embedded into a metric <i>X</i> with low distortion <i>c</i>. This is beneficial if one can guarantee low distortion for all metrics <i>Y</i> in <i>C</i>. However, in any situations, the worst-case distortion is too large to be meaningful. For example, if <i>X</i> is a line metric, then even very simple metrics (an <i>n</i> - point star or an <i>n</i> -point cycle) are embeddable into <i>X</i> only with distortion linear in <i>n</i>. 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 <i>X</i> from <i>C</i> as an input, finds an embedding of <i>X</i> into <i>Y</i> which has distortion <i>a</i> *<i>c</i><inf><i>Y</i></inf> (<i>X</i>), where <i>c</i><inf><i>Y</i></inf> (<i>X</i>)is the best possible distortion of an embedding of <i>X</i> into <i>Y</i>.In this paper we show algorithms and hardness results for relative embedding problems.In particular we give: •an algorith that, given a general metric <i>M</i>, finds an embedding with distortion <i>O</i> (Δ<sup>3⁄4</sup> poly(<i>c</i> <i><inf>line</inf></i> (<i>M</i>))), where Δ is the spread of <i>M</i>•an algorithm that,given a weighted tree etric <i>M</i>, finds an embedding with distortion poly(<i>c</i> <inf><i>line</i></inf> (<i>M</i>)) •a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor polynomial in <i>n</i>,even for weighted tree metrics with spread Δ=<i>n</i> <i><sup>O</sup></i> (1).