論文

査読有り
2003年3月

A primal-dual approximation algorithm for the survivable network design problem in hypergraphs

DISCRETE APPLIED MATHEMATICS
  • L Zhao
  • ,
  • H Nagamochi
  • ,
  • T Ibaraki

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.

リンク情報
DOI
https://doi.org/10.1016/S0166-218X(02)00201-9
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000180274300008&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/S0166-218X(02)00201-9
  • ISSN : 0166-218X
  • Web of Science ID : WOS:000180274300008

エクスポート
BibTeX RIS