Directed spanners via flow-based linear programs
Directed spanners via flow-based linear programs
复制标题
通过基于流程的线性程序定向扳手
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Robert Krauthgamer
中科院分区：
文献类型：
--
作者：
M. Dinitz;Robert Krauthgamer
我们通过基于流的线性规划松弛检查有向空间。我们设计了一个~O（n ~ 2/3）-逼近算法，它对所有k ≥ 1都有效，这是对任意边长的第一次次线性逼近.即使在更严格的单位边长设置中，当k ≥ 4时，我们的算法也优于以前的~O（n1-1/k）近似[BGJRW 09]。对于k=3的特殊情况，我们设计了一个不同的算法，实现了~O（n）-近似，改进了以前的~O（n2/3）[EP 05，BGJRW 09]（独立于我们的工作，最近设计了~O（n1-1/n k/2 n）[BRR 10]）。我们的算法很容易扩展到容错设置，最近引起了人们的注意，但不是从近似的角度来看。对任意常数ε > 0，我们还证明了~Ω（n1/3 - ε）的一个近似匹配的积分间隙.我们所有算法的优点是它们相对简单。从技术上讲，我们引入了一个新的但自然的基于流的松弛，并展示了如何近似解决它，即使它的大小不是多项式。主要的挑战是设计一个四舍五入的计划，“协调”之间的许多需求对流路径的选择，而使用很少的边缘整体。粗略地说，我们通过在顶点级别上进行随机化来实现这一点。
We examine directed spanners through flow-based linear programming relaxations. We design an ~O(n2/3)-approximation algorithm for the directed k-spanner problem that works for all k ≥ 1, which is the first sublinear approximation for arbitrary edge-lengths. Even in the more restricted setting of unit edge-lengths, our algorithm improves over the previous ~O(n1-1/k) approximation [BGJRW09] when k ≥ 4. For the special case of k=3 we design a different algorithm achieving an ~O(√n)-approximation, improving the previous ~O(n2/3) [EP05,BGJRW09] (independently of our work, an ~O(n1-1/⌈ k/2⌉) was recently devised [BRR10]). Both of our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. We also prove a nearly matching integrality gap of ~Ω(n1/3 - ε) for every constant ε > 0. A virtue of all our algorithms is that they are relatively simple. Technically, we introduce a new yet natural flow-based relaxation, and show how to approximately solve it even when its size is not polynomial. The main challenge is to design a rounding scheme that "coordinates" the choices of flow-paths between the many demand pairs while using few edges overall. We achieve this, roughly speaking, by randomization at the level of vertices.