论文标题
$（1.5+ε）$ - 加权连接性增强的近似算法
A $(1.5+ε)$-Approximation Algorithm for Weighted Connectivity Augmentation
论文作者
论文摘要
连接增强问题是网络设计中最基本问题之一。这些问题中的许多人承认自然$ 2 $ 2 $ - 附属算法通常是通过各种经典技术，而是否可以实现低于$ 2 $的近似因素。其最基本的示例之一是加权连接增强问题（WCAP）。在WCAP中，给出了一个无向图和一组额外的加权候选边缘，其任务是找到一组最便宜的候选边缘，其添加在图形上会增加其边缘连接性。我们提出了$（1.5+ \ varepsilon）$ - WCAP的近似算法，首次表明可以实现低于$ 2 $的因素。 在高水平上，我们设计了一个精心挑选的本地搜索算法，灵感来自最近加权树的进步。为了衡量进度，我们考虑了WCAP的定向削弱，并表明它具有高度结构化的平面解决方案。将原始问题的解决方案解释为一种定向弱化的解决方案，使我们能够以干净且算法的方式描述本地交换步骤。利用这些见解，我们表明我们可以在组件类中有效地搜索与圆形图的有界树宽子图密切相关的链接集中的良好交换步骤。此外，我们证明可以将最佳解决方案分解为较小的组件，只要我们尚未实现要求的近似保证，至少一个可以导致良好的本地搜索步骤。
Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural $2$-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation factors below $2$ can be achieved. One of the most basic examples thereof is the Weighted Connectivity Augmentation Problem (WCAP). In WCAP, one is given an undirected graph together with a set of additional weighted candidate edges, and the task is to find a cheapest set of candidate edges whose addition to the graph increases its edge-connectivity. We present a $(1.5+\varepsilon)$-approximation algorithm for WCAP, showing for the first time that factors below $2$ are achievable. On a high level, we design a well-chosen local search algorithm, inspired by recent advances for Weighted Tree Augmentation. To measure progress, we consider a directed weakening of WCAP and show that it has highly structured planar solutions. Interpreting a solution of the original problem as one of this directed weakening allows us to describe local exchange steps in a clean and algorithmically amenable way. Leveraging these insights, we show that we can efficiently search for good exchange steps within a component class for link sets that is closely related to bounded treewidth subgraphs of circle graphs. Moreover, we prove that an optimum solution can be decomposed into smaller components, at least one of which leads to a good local search step as long as we did not yet achieve the claimed approximation guarantee.
