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$.
翻译:我们认为连接增强问题(CAP)是统一网络设计领域一个典型的问题。这是一个在可生存的网络设计领域的典型问题。它涉及以最廉价的方式增加一个单位的图表的边际连接性。更准确地说,考虑到一个以美元为顶尖的相联图形$G=(V,E)和一组额外的边端,我们的任务是找到一个最起码的基点子子,其中加到G$的外端点使图(k+1美元)相联。如果美元是奇数,问题就在于如何降低树强化问题(TAP)的边际连接性。也就是说,G$是一棵横贯的树,最近已经取得了显著的进展,导致1.5美元(目前的最佳因素是1.458美元 ) 。然而,TAP的进展并没有一直持续到CAP的顶端端点。 事实上,直到最近,Byrka, Grandoni, 和Amelili (STOC 2020) 才能获得第一个低于2美元的基点的基点, 也就是我们第一次提出191美元为顶端的基点,因此, 美元为GG$为底的基价的基点算算。