论文标题
相对可生存的网络设计
Relative Survivable Network Design
论文作者
论文摘要
网络设计的最重要和研究的设置之一是边缘连接性要求。这包括统一的需求，例如最低$ k $ - 连接的跨越子图问题（$ k $ -ecss），以及非统一的需求，例如可生存的网络设计问题。但是，这些配方的弱点是，我们无法要求大于连通性大的耐断层。我们在相对容忍性的概念下介绍和研究这些问题的新变体。非正式地，如果存在有限数的故障（如经典设置），我们不要求连接两个节点，但是如果存在有界数的故障数，并且两个节点在基础图后的违规后违反后连接，则两个节点是连接的。也就是说，我们构建的子图必须与界故障后的连接性相同的基础图“行为”。 We define and introduce these problems, and provide the first approximation algorithms: a $(1+4/k)$-approximation for the unweighted relative version of $k$-ECSS, a $2$-approximation for the weighted relative version of $k$-ECSS, and a $27/4$-approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of $3$.为了获得这些结果，我们介绍了许多可能具有独立兴趣的技术思想。首先，我们对Ja那教的迭代式圆形分析进行概括，即使剪切函数并不是弱的超模型，但可以满足较弱的定义，我们引入并称呼局部局部弱的超模型性。其次，我们证明了一种结构定理，并设计了一种基于重要分离器的新分解的近似算法，该分离器是固定参数算法中常用的结构，这些结构通常在近似算法中常用。
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum $k$-Edge-Connected Spanning Subgraph problem ($k$-ECSS), as well as nonuniform demands such as the Survivable Network Design problem. A weakness of these formulations, though, is that we are not able to ask for fault-tolerance larger than the connectivity. We introduce and study new variants of these problems under a notion of relative fault-tolerance. Informally, we require not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. That is, the subgraph we build must "behave" identically to the underlying graph with respect to connectivity after bounded faults. We define and introduce these problems, and provide the first approximation algorithms: a $(1+4/k)$-approximation for the unweighted relative version of $k$-ECSS, a $2$-approximation for the weighted relative version of $k$-ECSS, and a $27/4$-approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of $3$. To obtain these results, we introduce a number of technical ideas that may of independent interest. First, we give a generalization of Jain's iterative rounding analysis that works even when the cut-requirement function is not weakly supermodular, but instead satisfies a weaker definition we introduce and term local weak supermodularity. Second, we prove a structure theorem and design an approximation algorithm utilizing a new decomposition based on important separators, which are structures commonly used in fixed-parameter algorithms that have not commonly been used in approximation algorithms.
