Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
复制标题
近似扳手和定向斯坦纳森林：上限和下限
DOI：
10.1145/3381451
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Laekhanukit, Bundit
中科院分区：
文献类型：
--
作者：
Chlamtáč, Eden;Dinitz, Michael;Kortsarz, Guy;Laekhanukit, Bundit
最近发现，加法扳手（所有距离都保留到加法拉伸的子图）、距离保护器（需求对的距离精确保留的子图）和成对扳手（需求对的距离保留到乘法或加法拉伸的子图）之间存在非常密切的联系 [Abboud-Bodwin SODA’16 8 J.ACM’17, Bodwin-Williams苏打'16]。我们从优化的角度研究这些问题，我们不是研究极值实例的存在，而是给我们一个实例，并要求我们找到尽可能稀疏的扳手/保护器。我们给出距离保持器和成对扳手的 O(n3/5 + ε) 近似值（对于任意常数 ε > 0）。这是这两个问题的第一个重要上限，众所周知，这两个问题都像标签覆盖一样难以近似。我们还证明了近似加性扳手的标签覆盖硬度，即使对于加性 1 拉伸（人们可能期望多对数近似，因为相关的乘法 2 扳手问题承认 O(logn) 近似）和加性多对数拉伸（其中相关的乘法扳手问题具有 O(1) 近似）的情况也是如此。有趣的是，我们在近似算法中使用的技术超出了基于距离的问题到纯连接网络设计问题。特别是，当所有边具有统一成本时，我们的技术允许我们为定向斯坦纳森林问题（对于任意常数 ε > 0）给出 O(n3/5 + ε) 近似，从而改进了 Berman 等人之前的最佳 O(n2/3 + ε) 近似。 [ICALP’11]（适用于一般边缘成本）。
It was recently found that there are very close connections between the existence ofadditive spanners(subgraphs where all distances are preserved up to an additive stretch),distance preservers(subgraphs in which demand pairs have their distance preserved exactly), andpairwise spanners(subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA’16 8 J.ACM’17, Bodwin-Williams SODA’16]. We study these problems from an optimization point of view, where rather than studying the existence of extremal instances, we are given an instance and are asked to find the sparsest possible spanner/preserver. We give anO(n3/5 + ε)-approximation for distance preservers and pairwise spanners (for arbitrary constant ε > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits anO(logn)-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has anO(1)-approximation).Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give anO(n3/5 + ε)-approximation for the Directed Steiner Forest problem (for arbitrary constant ε > 0) when all edges have uniform costs, improving the previous bestO(n2/3 + ε)-approximation due to Berman et al. [ICALP’11] (which holds for general edge costs).