2003年3月
A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
DISCRETE APPLIED MATHEMATICS
- ,
- ,
- 巻
- 126
- 号
- 2-3
- 開始ページ
- 275
- 終了ページ
- 289
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/S0166-218X(02)00201-9
- 出版者・発行元
- ELSEVIER SCIENCE BV
Given a hypergraph with nonnegative costs on hyperedges, and a weakly supermodular function r: 2(V) --> Z(+), where V is the vertex set, we consider the problem of finding a minimum cost subset of hyperedges such that for every set S subset of or equal to V, there are at least r(S) hyperedges that have at least one but no all endpoints in S. This problem captures a hypergraph generalization of the survivable network design problem (SNDP), and also the element connectivity problem (ECP). We present a primal-dual algorithm with a performance guarantee of d(max)(+) H(r(max)), where d(max)(+) is the maximum degree of hyperedges of positive costs, r(max) =max(S) r(S), and H(k)= 1 + 1/2 +(...)+ 1/k. In particular, our result contains a 2H(r(max))-approximation algorithm for ECP, which gives an independent and complete proof for the result first obtained by Jain et al. (Proceedings of the SODA, 1999, p. 484-489). (C) 2002 Elsevier Science B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/S0166-218X(02)00201-9
- ISSN : 0166-218X
- Web of Science ID : WOS:000180274300008