Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders
Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders
复制标题
图的最小失真欧几里得嵌入：循环和扩展器的乘积
DOI：
10.1006/jctb.2000.1953
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
A. Magen
中科院分区：
文献类型：
--
作者：
N. Linial;A. Magen
有限度量空间嵌入欧几里得空间的研究包括：巴纳赫空间的局部理论、近似算法的设计和图论。重点通常是嵌入尽可能少的失真。也就是说，我们寻求一个最小化映射的双lipschitz常数的嵌入。这个问题也被用于嵌入到其他赋范空间中。然而，当主机空间是l2时，更多的可以说：找到一个最优嵌入到l2的问题可以被表述为一个半确定的程序（因此可以在多项式时间内解决）。到目前为止，这个优雅的问题陈述还没有应用到任何有趣的显式实例中。在这里，我们采用这种方法并检验了两类图：(i)循环的乘积，和（ii）常次展开图。我们在(i)中的结果扩展了P. Enflo (1969, Ark) 30年前的结果。Mat.8, 103 - 105)在立方体上。我们在（ii）中的结果提供了另一种证明，证明存在n点度量空间，其欧几里德失真为- (logn)。此外，我们证明了类（ii）中的指标与类122的距离为- (logn)，即l2中可实现的指标的平方。这是一个经过充分研究的类，它包含所有l1指标（因此也包含所有l2指标）。我们的一些方法可以很好地应用于使用半定规划来估计欧几里德扭曲的更一般的实例。具体来说，我们开发了一种证明嵌入最优性的方法。在可能猜测最佳嵌入的情况下，这个想法很有用。
Embeddings of finite metric spaces into Euclidean space have been studied in several contexts: The local theory of Banach spaces, the design of approximation algorithms, and graph theory. The emphasis is usually on embeddings with the least possible distortion. That is, one seeks an embedding that minimizes the bi-Lipschitz constant of the mapping. This question has also been asked for embeddings into other normed spaces. However, when the host space is l2 , more can be said: The problem of finding an optimal embedding into l2 can be formulated as a semi-definite program (and can therefore be solved in polynomial time). So far, this elegant statement of the problem has not been applied to any interesting explicit instances. Here we employ this method and examine two families of graphs: (i) products of cycles, and (ii) constant-degree expander graphs. Our results in (i) extend a 30-year-old result of P. Enflo (1969, Ark. Mat.8, 103�105) on the cube. Our results in (ii) provide an alternative proof to the fact that there are n-point metric spaces whose Euclidean distortion is �(logn). Furthermore, we show that metrics in the class (ii) are �(logn) far from the class l22, namely, the square of the metrics realizable in l2. This is a well studied class which contains all l1 metrics (and therefore also all l2 metrics). Some of our methods may well apply to more general instances where semidefinite programming is used to estimate Euclidean distortions. Specifically, we develop a method for proving the optimality of an embedding. This idea is useful in those cases where it is possible to guess an optimal embedding.