论文标题
可生存的网络设计重新访问：小组连接性
Survivable Network Design Revisited: Group-Connectivity
论文作者
论文摘要
在经典的可生存网络设计问题（SNDP）中，我们获得了一个无方向的图形$ g =（v，e）$，边缘成本和连接性要求$ k（s，t）$，每对顶点。目的是找到一个最低成本的子图$ h \ subseteq v $，以使每个对$（s，t）$通过$ k（s，t）$ edge或（公开）顶点脱节路径连接，分别为EC-SNDP和VC-SNDP。 The seminal result of Jain [FOCS'98, Combinatorica'01] gives a $2$-approximation algorithm for EC-SNDP, and a decade later, an $O(k^3\log n)$-approximation algorithm for VC-SNDP, where $k$ is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS'09, Theory comput.'12]。尽管关于SNDP的点对点设置有丰富的文献，但在子集之间的可行连通性案例仍然相对较差。 本文涉及SNDP对子集到扣子设置的概括，即组EC-SNDP。我们开发了该框架，该框架产生了第一个非平地（真）近似算法的EC-SNDP。以前，只有双粒子近似算法以EC-SNDP [Chalermsook，Grandoni和Laekhanukit，Soda'15]而闻名，而真实的近似算法仅以单源量变体而闻名，该算法仅以连接性要求$ k（s，t）\ in \ in \ in \ in \ in \ in okish和krish和krish和krish， Ravi，Soda'10; Khandekar，Kortsarz和Nutov，FSTTCS'09和Theor。计算。 Sci.'12]。
In the classical survivable network design problem (SNDP), we are given an undirected graph $G=(V,E)$ with costs on edges and a connectivity requirement $k(s,t)$ for each pair of vertices. The goal is to find a minimum-cost subgraph $H\subseteq V$ such that every pair $(s,t)$ are connected by $k(s,t)$ edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS'98, Combinatorica'01] gives a $2$-approximation algorithm for EC-SNDP, and a decade later, an $O(k^3\log n)$-approximation algorithm for VC-SNDP, where $k$ is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS'09, Theory Comput.'12]. While there is rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This paper concerns the generalization of SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA'15], and a true approximation algorithm is known only for the single-source variant with connectivity requirement $k(S,T)\in\{0,1,2\}$ [Gupta, Krishnaswamy, and Ravi, SODA'10; Khandekar, Kortsarz, and Nutov, FSTTCS'09 and Theor. Comput. Sci.'12].
