论文标题
超级线性时间内直径的不XBIBIBIBIBITE：超出5/3的比率
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
论文作者
论文摘要
我们表明，假设有很强的指数时间假设，对于每一个$ \ varepsilon> 0 $，近似于$ 7/4- $ 7/4- \ VAREPSILON $在$ m $ -M $ -ARC图上近似于定向直径，需要$ M^{4/3- o（1）} $。我们的施工使用非负边缘的权重，但甚至适用于稀疏的挖掘物，即为此，顶点$ n $的数量和Arcs $ M $满足的数量$ m = n \ log^{o（1）} n $。这是有条件排除直径$ 5/3 $ APPROXIMATION的第一个结果。
We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices $n$ and the number of arcs $m$ satisfy $m = n \log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter.
