论文标题
灵活网络设计的基于增强的近似算法
Augmentation based Approximation Algorithms for Flexible Network Design
论文作者
论文摘要
Adjshvili以非均匀故障模型引入了网络设计：给定图的边缘集分为安全且不安全的边缘。一个顶点对$（s，t）$是$（p，q）$ - 如果$ s $和$ t $具有$ p $ edge-connectivity，即使删除了任何$ q $ $ q $不安全的边缘，也有连接。给定图形$ g $，目标是选择一个为给定的顶点对带来的flex连接性的$ g $ $ g $的$ h $ h $。该模型概括了基于良好的边缘连接性网络设计，但是，即使是特殊情况也更难近似。 该模型中网络设计的近似性主要研究了两个感兴趣的设置：（i）以FTP和FTF的名称（耐受耐受性路径和容错流）为单一对设置，（ii）跨越名称fgc（灵活的图形连接性）的跨度设置。这些论文有几个积极的结果。但是，尽管与众所周知的网络设计问题相似，但这种新模型在设计近似算法方面一直具有挑战性，尤其是当$ p，q \ ge 2 $时。我们获得了两个结果，可以提高我们对该模型中算法设计的理解。 1。我们获得了$（2,2）$ - 单对$（S，T）$的$（2,2）$ - flex连接性的$ 5 $。以前在此设置中不知道非平凡的近似。 2。我们获得$ O（p）$（P，2）$和$（P，3）$ -FGC的任何$ p \ ge 1 $，以及$（P，4）$ -FGC的任何$ P $。我们获得$ O（q）$ - $（2，Q）$ - fgc的近似，任何$ q \ ge 1 $。以前只有$ O（q \ log n）$ - 这些设置已知。 我们的结果是通过增强框架获得的，在该框架中，我们确定了一种结构化的方式，可以使用众所周知的$ 2 $ Approximation来覆盖不易碎的削减家庭。我们的分析还证明了我们制定的LP松弛的相应的完整性差距。
Adjiashvili introduced network design in a non-uniform fault model: the edge set of a given graph is partitioned into safe and unsafe edges. A vertex pair $(s,t)$ is $(p,q)$-flex-connected if $s$ and $t$ have $p$ edge-connectivity even after the removal of any $q$ unsafe edges. Given a graph $G$, the goal is to choose a min-cost subgraph $H$ of $G$ that has desired flex-connectivity for a given set of vertex pairs. This model generalizes the well-studied edge-connectivity based network design, however, even special cases are provably much harder to approximate. The approximability of network design in this model has been mainly studied for two settings of interest: (i) single pair setting under the names FTP and FTF (fault tolerant path and fault tolerant flow), (ii) spanning setting under the name FGC (flexible graph connectivity). There have been several positive results in these papers. However, despite similarity to the well-known network design problems, this new model has been challenging to design approximation algorithms for, especially when $p,q \ge 2$. We obtain two results that advance our understanding of algorithm design in this model. 1. We obtain a $5$-approximation for the $(2,2)$-flex-connectivity for a single pair $(s,t)$. Previously no non-trivial approximation was known for this setting. 2. We obtain $O(p)$ approximation for $(p,2)$ and $(p,3)$-FGC for any $p \ge 1$, and for $(p,4)$-FGC for any even $p$. We obtain an $O(q)$-approximation for $(2,q)$-FGC for any $q \ge 1$. Previously only a $O(q \log n)$-approximation was known for these settings. Our results are obtained via the augmentation framework where we identify a structured way to use the well-known $2$-approximation for covering uncrossable families of cuts. Our analysis also proves corresponding integrality gap bounds on an LP relaxation that we formulate.
