On average distortion of embedding metrics into the line and into L1
On average distortion of embedding metrics into the line and into L1
复制标题
将度量嵌入到线路和 L1 中的平均失真
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Yuri Rabinovich
中科院分区：
文献类型：
--
作者：
Yuri Rabinovich
我们引入并研究了一个度量空间到另一个度量空间的非扩张嵌入的平均失真概念。平均失真不如乘法度量失真敏感，它能很好地捕捉全局情况，而且总体而言，它是一种非常有趣的度量接近性的新度量，与测度集中现象有关。我们在均匀需求多商品流中的最小割 - 最大流差距和将合适的（对偶）度量嵌入到\(l_1\)空间的平均失真之间建立了紧密的相互关系。利用这些关系表明，特殊（例如，平面图、有界树宽图等）图的最短路径度量以常数平均失真嵌入到\(l_1\)空间。本文的主要结果声称，即使将\(l_1\)替换为直线，这仍然成立。对于有界树宽的图，这个结果进一步得到了强化。
We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture, and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. We establish close mutual relations between the MinCut- MaxFlow gap in a uniform-demand multicommodity flow, and the average distortion of embedding the suitable (dual) metric into l1. These relations are exploited to show that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) graphs embed into l1 with constant average distortion. The main result of the paper claims that this remains true even if l1 is replaced with the line. This result is further sharpened for graphs of a bounded treewidth.