Approximation Algorithms for Min-Distance Problems

Approximation Algorithms for Min-Distance Problems
复制标题

小距离问题的近似算法

DOI：
10.4230/lipics.icalp.2019.46
复制
发表时间：
2019
期刊：
ArXiv
影响因子：
--
通讯作者：
Yuancheng Yu
Yuancheng Yu
中科院分区：
--
文献类型：
--
作者：
M. Dalirrooyfard;V. V. Williams;Nikhil Vyas;Nicole Wein;Yinzhan Xu;Yuancheng Yu

文献摘要

被引文献

相似文献

我们研究基本的图参数，如有向图中的直径和半径，当距离是用一种有点非正统但自然的度量来测量时：$u$和$v$之间的距离是从$u$到$v$和$v$到$u$的最短路径距离的最小值。例如，在这种度量下，图中的中心节点可以代表医院的最佳位置，以确保每个人都能获得最快的医疗服务，因为一个人可以去医院，也可以派医生来帮忙。 通过计算所有对最短路径，我们研究的所有对距离和参数都可以在$\tilde{O}(mn)$时间内精确地计算出$n$顶点、$m$边和非负边权的有向图。此外，在强指数时间假设下，这个时间限制是严格的[Roditty-Vassilevska W. STOC 2013]，因此研究这些参数在$O(mn^{1-\epsilon})$时间内对常数$\epsilon>0$的近似程度是很自然的。Abboud， Vassilevska Williams和Wang [SODA 2016]给出了直径和半径的多项式因子近似值，以及在图是DAG的特殊情况下两个问题的常数因子近似值。我们通过提供一般图中直径、半径和相关偏心问题的第一个常数因子近似，大大改进了这些边界。此外，我们还为Diameter提供了一个算法层次结构，以权衡时间和精度。
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance between $u$ and $v$ is the minimum of the shortest path distances from $u$ to $v$ and from $v$ to $u$. The center node in a graph under this measure can for instance represent the optimal location for a hospital to ensure the fastest medical care for everyone, as one can either go to the hospital, or a doctor can be sent to help. By computing All-Pairs Shortest Paths, all pairwise distances and thus the parameters we study can be computed exactly in $\tilde{O}(mn)$ time for directed graphs on $n$ vertices, $m$ edges and nonnegative edge weights. Furthermore, this time bound is tight under the Strong Exponential Time Hypothesis [Roditty-Vassilevska W. STOC 2013] so it is natural to study how well these parameters can be approximated in $O(mn^{1-\epsilon})$ time for constant $\epsilon>0$. Abboud, Vassilevska Williams, and Wang [SODA 2016] gave a polynomial factor approximation for Diameter and Radius, as well as a constant factor approximation for both problems in the special case where the graph is a DAG. We greatly improve upon these bounds by providing the first constant factor approximations for Diameter, Radius and the related Eccentricities problem in general graphs. Additionally, we provide a hierarchy of algorithms for Diameter that gives a time/accuracy trade-off.