Approximating connectivity augmentation problems
Approximating connectivity augmentation problems
复制标题
近似连接增强问题
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Zeev Nutov
中科院分区：
文献类型：
--
作者：
Zeev Nutov
设<i>G</i> =（<i>V，E</i>）是一个图，<i>S</i> ∈ <i>V. </i><i>G</i>中<i>u</i>和<i>v</i>的<i>S-连通度</i>λ<i>s</i>（<i>u，v; G</i>）是指在<i>S</i>- {<i>u，v</i>}中没有两条uv -路有公共边或公共结点的最大<i>uv</i>-路数。相应的<i>连通性扩充问题（CAP）</i>是：给定一个图<i>G</i>=（<i>V，E</i>），一个节点子集<i>S</i><$<i>V</i>，以及一个节点对集合上的非负整数要求函数<i>r</i>（<i>u，v</i>），给<i>G</i>增加一个新边的最小大小集合<i>F</i>，使得λ<i>s</i>（<i>u，v; G</i>+<i>F</i>）≥<i>r</i>（<i>u，v</i>）对所有<i>u，v</i>∈<i>V</i>成立。三种被广泛研究的特殊情况是：<i>边-</i>（<i>S</i>= θ），<i>节点-</i>（<i>S = V</i>），和<i>元素-</i>（<i>r</i>（<i>u，v</i>）= 0，只要<i>u</i>∈<i>S</i>或<i>v</i>∈<i>S</i>）CAP。提出了一种求解边缘CAP的多项式算法.弗兰克[8]。本文考虑了即使对<i>r</i>（<i>u，v</i>）∈ {0，2}也是NP-困难的元素CAP和节点CAP。我们的主要结果是一个7/4近似算法的元素CAP，提高了以前最好的已知的2近似。对于{0，<i>k</i>}-元CAP（其中<i>r</i>（<i>u，v</i>）∈ {0，<i>k</i>}）和{0，1，2}-元CAP，我们给出了一个3/2-近似算法.近似比是基于一个新的下界的边缘的数量需要覆盖一个斜超模集函数。对于node-CAP，我们建立了以下近似阈值：对于任何固定的∈ > 0，{0，<i>k</i>}-node-CAP不能在<i>O</i>（2<sup>log-1-∈<i>n</i></sup>）内近似，除非NP ≠ DTIME（<i>n</i><sup>Polylog（<i>n</i>）</sup>）;因此node-CAP不太可能具有多对数近似。
Let <i>G</i> = (<i>V, E</i>) be a graph and let <i>S</i> ⊆ <i>V.</i> The <i>S-connectivity</i> λ<i>s</i>(<i>u, v; G</i>) of <i>u</i> and <i>v</i> in <i>G</i> is the maximum number of <i>uv</i>-paths that no two of them have an edge or a node in <i>S</i> - {<i>u, v</i>} in common. The corresponding <i>Connectivity Augmentation Problem (CAP)</i> is: given a graph <i>G</i> = (<i>V, E</i>), a node subset <i>S</i> ⊆ <i>V</i>, and a nonnegative integer requirement function <i>r</i>(<i>u, v</i>) on the set of pairs of nodes, add a minimum size set <i>F</i> of new edges to <i>G</i> so that λ<i>s</i>(<i>u, v; G</i> + <i>F</i>) ≥ <i>r</i>(<i>u, v</i>) holds for all <i>u, v</i> ∈ <i>V</i>. Three extensively studied particular cases are: the <i>edge-</i> (<i>S</i> = θ), the <i>node-</i> (<i>S = V</i>), and the <i>element-</i> (<i>r</i>(<i>u, v</i>) = 0 whenever <i>u</i> ∈ <i>S</i> or <i>v</i> ∈ <i>S</i>) CAP. A polynomial algorithm for edge- CAP was developed by A. Frank [8]. In this paper we consider the element-CAP and the node-CAP, that are NP- hard even for <i>r</i>(<i>u, v</i>) ∈ {0, 2}. Our main result is a 7/4- approximation algorithm for the element-CAP, improving the previously best known 2-approximation. For the {0, <i>k</i>}- element-CAP (with <i>r</i>(<i>u, v</i>) ∈ {0, <i>k</i>}) and for the {0, 1, 2}-element-CAP we give a 3/2-approximation algorithm. The approximation ratios are based on a new lower bound on the number of edges needed to cover a skew-supermodular set function. For the node-CAP we establish the following approximation threshold: the {0, <i>k</i>}-node-CAP cannot be approximated within <i>O</i>(2<sup>log-1-∈<i>n</i></sup>) for any fixed ∈ > 0, unless NP ⊆ DTIME(<i>n</i><sup>Polylog(<i>n</i>)</sup>); thus the node-CAP is unlikely to have a polylogarithmic approximation.