论文标题
通过基于räcke树的圆形近似柔性图连接
Approximating Flexible Graph Connectivity via Räcke Tree based Rounding
论文作者
论文摘要
灵活的图形连接是Adjshvili介绍的一种新的网络设计模型。它已经看到了最近的一些算法进步。尽管如此，即使在单对$（s，t）$的情况下，近似性也很差。在我们最近的工作中，我们提出了一个问题，即当连接性要求是固定的常数时，生存的网络设计版本（FLEX-SNDP）是否有多层近似。在本文中，我们为Chen，Laekhanukit，Liao和Zhang最近开发的可生存网络设计改编了一个强大的框架，以对这个问题给出肯定的答案。 IS的框架基于Räcke树和组施泰纳树的圆形。该算法和分析还建立了flex-SNDP LP弛豫的整体差距的上限。
Flexible graph connectivity is a new network design model introduced by Adjiashvili. It has seen several recent algorithmic advances. Despite these, the approximability even in the setting of a single-pair $(s,t)$ is poorly understood. In our recent work, we raised the question of whether there is poly-logarithmic approximation for the survivable network design version (Flex-SNDP) when the connectivity requirements are fixed constants. In this paper, we adapt a powerful framework for survivable network design recently developed by Chen, Laekhanukit, Liao, and Zhang to give an affirmative answer to the question. The framework of is based on Räcke trees and group Steiner tree rounding. The algorithm and analysis also establishes an upper bound on the integrality gap of an LP relaxation for Flex-SNDP.
