论文标题
连通性增强问题的近似算法
Approximation algorithms for connectivity augmentation problems
论文作者
论文摘要
在连接增强问题中，我们得到了图形$ h =（v，e_h）$和$ v $上的边缘集$ e $，并寻求一个最小的边缘套装$ j \ subseteq e $ $，因此$ h \ cup j $具有比$ h $更大的边缘/节点连接。在边缘连接性增强问题中，我们需要将边缘连接性增加$ 1 $。在Block-Tree增强问题中，$ H $已连接，$ H \ Cup S $应为$ 2 $连接。在叶到叶连接性增强问题中，$ e $中的每个边缘都连接最小的缺陷集。对于此版本，我们给出了一个简单的组合近似算法，比率为$ 5/3 $，改善了适用于一般情况的$ 1.91 $近似值。我们还通过一个简单的证据表明，如果施泰纳树问题承认近似值$α$，那么一般版本的近似值$ 1+\ ln（4-x）+ε$，其中$ x $是方程$ 1+\ ln（4-x）=α+（α+（α-α-1）x $的解决方案。对于$α= \ ln 4+ε$的当前最佳价值，这给出了比率$ 1.942 $。这比最佳比率$ 1.91 $稍差，但具有将Steiner树近似作为“黑匣子”的优势，如果可以实现比率$ <leq 1.35 $的比率$ <1.9 $。 在“元素连接增强问题”中，我们得到了一个图$ g =（v，e）$，$ s \ subseteq v $和连接要求$ \ {r（u，v）：u，v \ in s \} $。目标是在$ s $上找到一个最小的新边缘的$ j $，以便对于所有$ u，v \ in s $ the Graph $ g \ cup j $包含$ r（u，v）$ $ $ $ uv $ path，因此没有两个在$ v \ setminus s $中都具有Edge或一个节点。即使$ \ max_ {u，v \ in s} r（u，v）= 2 $，问题也是np-hard。我们获得近似值$ 3/2 $，提高了先前的比率$ 7/4 $。
In Connectivity Augmentation problems we are given a graph $H=(V,E_H)$ and an edge set $E$ on $V$, and seek a min-size edge set $J \subseteq E$ such that $H \cup J$ has larger edge/node connectivity than $H$. In the Edge-Connectivity Augmentation problem we need to increase the edge-connectivity by $1$. In the Block-Tree Augmentation problem $H$ is connected and $H \cup S$ should be $2$-connected. In Leaf-to-Leaf Connectivity Augmentation problems every edge in $E$ connects minimal deficient sets. For this version we give a simple combinatorial approximation algorithm with ratio $5/3$, improving the previous $1.91$ approximation that applies for the general case. We also show by a simple proof that if the Steiner Tree problem admits approximation ratio $α$ then the general version admits approximation ratio $1+\ln(4-x)+ε$, where $x$ is the solution to the equation $1+\ln(4-x)=α+(α-1)x$. For the currently best value of $α=\ln 4+ε$ this gives ratio $1.942$. This is slightly worse than the best ratio $1.91$, but has the advantage of using Steiner Tree approximation as a "black box", giving ratio $< 1.9$ if ratio $α\leq 1.35$ can be achieved. In the Element Connectivity Augmentation problem we are given a graph $G=(V,E)$, $S \subseteq V$, and connectivity requirements $\{r(u,v):u,v \in S\}$. The goal is to find a min-size set $J$ of new edges on $S$ such that for all $u,v \in S$ the graph $G \cup J$ contains $r(u,v)$ $uv$-paths such that no two of them have an edge or a node in $V \setminus S$ in common. The problem is NP-hard even when $\max_{u,v \in S} r(u,v)=2$. We obtain approximation ratio $3/2$, improving the previous ratio $7/4$.
