近似最短路径 (9)

11.9 赋距空间与 L1 嵌入的 Bourgain 定理

图上的距离也满足赋距空间(metric space)的定义：非负距离、对称性、递移律、三角不等式。
如果我们将图上的点对应到 k 维的向量空间，那麽只要 k 足够小，就可以很有效率地计算近似距离。

k 维向量空间的 L1距离是这样定义的：把每一个维度数字相差的绝对值累加起来，就是距离。
今天来说说一个把任意赋距空间投射到 O(log^2 n) 维度的 L1距离之向量空间，且距离的误差不超过原先的 O(log n) 倍的 Bourgain 定理(证明略)：

对於所有 i=1, 2, …, log n 以及 j = 1, 2, …, 1000 log n；我们以 2^{-i} 的机率(这个机率只与 i 有关、与 j 无关) 均匀取样图上的点集合 A_ij。接着，对於图上每一个点 x，我们定义 k=1000 * log^2 n 维度的向量：第 (i, j) 维度的数值就是 x 到 A_ij 之间的点集合任一点的最短距离 dist(x, A_ij)。

这个方法建构出来的向量，要表达它也需要 O(log^3 n)-bits，误差在计算距离且除以 log n 之後也为 O(log n)，不过它不只适用於任何图，也适用於任何 n 笔资料的赋距空间，相当巧妙。

除了 L1 距离，Bourgain 的定理也适用於任何的 Lp-距离 (只有误差要稍微调整一下，但仍为 O(log n))。

参考资料：
https://lucatrevisan.github.io/teaching/expanders2016/lecture10.pdf