An optimal algorithm for average distance in typical regular graphs
Alexandros Eskenazis, Manor Mendel, Assaf Naor
我们设计了一个确定性算法,在典型的恒定度正则图中给定n点,查询O(n)距离以输出这些点之间的平均距离的恒定因子近似,从而回答<cit.>提出的问题。 我们的算法使用 <cit.> 的方法构建了一系列恒定度图,这些图形是相对于某些非正向弯曲度量空间的扩展器,以及用于非正向弯曲度量空间的度量变换的新刚度定理。 我们的算法适用于典型的(均匀随机的)恒定度正则图形而不是所有恒定度图的事实是不可避免的,这要归功于我们获得的以下不可能结果:对于每个固定的k∈,对于所有恒定度图和查询 o(n^1+1/k) 的平均距离的任何算法的近似因子必须至少为2(k+1)。 这与为<cit.>中的一般有限度量空间设计的算法实现的上限边界相匹配。 因此,在近似保证小于4的恒定度图中的平均距离的任何算法都必须查询Ω(n^2)距离,任何近似保证小于6的算法都必须查询Ω(n^3/2)距离,任何近似保证小于8的算法必须查询Ω(n^4/3)距离,等等,并且还有算法实现这些参数。
We design a deterministic algorithm that, given n points in a typical constant degree regular graph, queries O(n) distances to output a constant factor approximation to the average distance among those points, thus answering a question posed in <cit.>. Our algorithm uses the method of <cit.> to construct a sequence of constant degree graphs that are expanders with respect to certain nonpositively curved metric spaces, together with a new rigidity theorem for metric transforms of nonpositively cu...