论文标题
弥合树木和连通性增强之间的差距：统一和更强的方法
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
论文作者
论文摘要
我们考虑了连接增强问题（CAP），这是可生存网络设计领域的经典问题。这是关于以最便宜的方式增加一个单元的边缘连接性。更确切地说，给定$ k $连接的图形$ g =（v，e）$和一组额外的边缘，其任务是找到一个最小的基数子集的额外边缘的最小值子集，其在$ g $中增加了图形$（k+1）$ - 边缘连接。如果$ k $很奇怪，则已知该问题将减少到树木膨胀问题（TAP） - 即，$ g $是一棵生成树 - 最近取得了重大进展，导致近似于$ 1.5 $的近似因素（当前最佳因素为$ 1.458 $）。但是，TAP上的进步并没有延续到更远的地方。的确，直到最近，拜尔卡，格兰多尼和阿米利（Stoc 2020）才通过基于与最近的TAP前进的方法脱离了一种方法，通过提供了1.91美元的Approximation算法来获得第一个近似值低于$ 2 $的CAP $ 2 $。 我们首先通过提出允许利用Tap和接近CAP的洞察力的技术来弥合水龙头和帽之间的缝隙。然后，我们引入了一种基于新的分析技术的新方法，以使近似因子低于$ 1.5 $。通过这些成分，我们获得了$ 1.393 $ - APPROXIMATION算法的CAP，因此也可以点击。这可以以统一的方式导致目前最佳的近似结果，这是通过上述$ 1.91 $ - 盖帽的$ 1.458 $ 1.458 $ 1.458 $ 1.458 $的最佳提高，grandoni，kalaitzis，kalaitzis和zenklusen（Zenklusen）（Stoc 2018）。此外，我们从最近的TAP进步中继承的功能是，当最大链接上最大成本与最小成本之间的比率有限时，我们的方法可以处理加权设置，在这种情况下，我们获得了低于$ 1.5 $的近似值。
We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a $k$-edge-connected graph $G=(V,E)$ and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to $G$ makes the graph $(k+1)$-edge-connected. If $k$ is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP) -- i.e., $G$ is a spanning tree -- for which significant progress has been achieved recently, leading to approximation factors below $1.5$ (the currently best factor is $1.458$). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below $2$ for CAP by presenting a $1.91$-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below $1.5$, based on a new analysis technique. Through these ingredients, we obtain a $1.393$-approximation algorithm for CAP, and therefore also TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned $1.91$-approximation for CAP and also the previously best approximation factor of $1.458$ for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below $1.5$.
