首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
  • 本地全文:下载
  • 作者:Julia Chuzhoy ; Sanjeev Khanna
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2012
  • 卷号:8
  • 页码:401-413
  • 出版社:University of Chicago
  • 摘要:

    In the Survivable Network Design Problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with an integer connectivity requirement $r(u,v)$ for each pair $u, v$ of vertices. The goal is to find a minimum-cost subset $E^*$ of edges such that in the subgraph of $G$ induced by $E^*$, each pair $u, v$ of vertices is $r(u,v)$-connected. In the edge-connectivity version, a pair $u, v$ is $r(u,v)$-connected if there are $r(u,v)$ edge-disjoint paths between $u$ and $v$. Similarly, in the vertex-connectivity version, a pair $u, v$ is $r(u,v)$-connected if there are $r(u,v)$ vertex-disjoint paths between $u$ and $v$. The edge-connectivity version of SNDP is known to have a factor 2 approximation. However, no non-trivial approximation algorithm has been known so far for the vertex version of SNDP, except for special cases of the problem.

    We present an extremely simple randomized algorithm that achieves an $O(k^3 \log |T|)$-approximation for this problem, where $k$ denotes the maximum connectivity requirement, and $T$ is the set of vertices that participate in one or more pairs with non-zero connectivity requirements. We also give a simple proof of the recently discovered $O(k^2 \log |T|)$-approximation algorithm for the single-source version of vertex-connectivity SNDP. Our results establish a natural connection between vertex-connectivity and a well-understood generalization of edge-connectivity, namely, element-connectivity, in that an instance of vertex-connectivity SNDP can be reduced to a small number of instances of the element-connectivity SNDP.

    A preliminary version of this paper appeared in the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009.

  • 关键词:approximation algorithms; survivable network design; vertex-connectivity
国家哲学社会科学文献中心版权所有