论文标题
节点连接性终端备份，分别启用的多圈和离散的凸度
Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity
论文作者
论文摘要
终端备份问题（Anshelevich和Karagiozova（2011））形成了一类网络设计问题：给定终端需要的无向图，目标是找到满足连接性要求的最低成本子图。节点连接性终端备份问题需要一个终端将其他终端连接到许多节点 - 偶发路径。这个问题尚不清楚是NP-HARD还是可处理的。 Fukunaga（2016）使用General LP-Solver提供了基于LP-ROUNDING计划的$ 4/3 $ APPRXIMATION算法。在本文中，我们为放松的LP开发了一种组合算法，以在$ o（m \ log（nua）\ cdot \ cdot \ perpopatorname {mf}（mf}（kn，m+k^2n）$时间）中找到半积分的最佳解决方案，$ n $是$ m $是$ n $ quard，$是$ k $ k $ k，边缘成本，$ u $是最大边缘容量，而$ \ operatorname {mf}（n'，m'）$是具有$ n $ nodes和$ m'$ edge网络中最大流量算法的时间复杂性。该算法意味着，还有效地实现了节点连接性终端备份问题的$ 4/3 $ - APPROXIMATION算法。对于算法的设计，我们探讨了节点连接性终端问题与新型的多动类型（称为单独录制的多圈）之间的连接。我们显示了一个最小的最大定理，该定理将Lovás-Cherkassky定理扩展到节点容量设置。我们的结果基于节点连接性终端备份问题的离散凸度。
The terminal backup problems (Anshelevich and Karagiozova (2011)) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga (2016) gave a $4/3$-approximation algorithm based on LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in $O(m\log (nUA)\cdot \operatorname{MF}(kn,m+k^2n))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $A$ is the maximum edge-cost, $U$ is the maximum edge-capacity, and $\operatorname{MF}(n',m')$ is the time complexity of a max-flow algorithm in a network with $n'$ nodes and $m'$ edges. The algorithm implies that the $4/3$-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, called a separately-capacitated multiflow. We show a min-max theorem which extends Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.
