2002年5月
A 2-approximation algorithm for the minimum weight edge dominating set problem
DISCRETE APPLIED MATHEMATICS
- ,
- 巻
- 118
- 号
- 3
- 開始ページ
- 199
- 終了ページ
- 207
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/S0166-218X(00)00383-8
- 出版者・発行元
- ELSEVIER SCIENCE BV
We present a polynomial-time algorithm approximating the minimum weight edge dominating set problem within a factor of 2. It has been known that the problem is NP-hard but, when edge weights are uniform (so that the smaller the better), it can be efficiently approximated within a factor of 2. When general weights were allowed, however, very little had been known about its approximability, and only very recently was it shown to be approximable within a factor of 2 1/10 by reducing to the edge cover problem via LP relaxation. In this paper we extend the approach given therein, by studying more carefully polyhedral structures of the problem, and obtain an improved approximation bound as a result. While the problem considered is as hard to approximate as the weighted vertex cover problem is, the best approximation (constant) factor known for vertex cover is 2 even for the unweighted case, and has not been improved in a long time, indicating that improving our result would be quite difficult. (C) 2002 Elsevier Science B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/S0166-218X(00)00383-8
- DBLP
- https://dblp.uni-trier.de/rec/journals/dam/FujitoN02
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000174769500003&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/dam/dam118.html#journals/dam/FujitoN02
- ID情報
-
- DOI : 10.1016/S0166-218X(00)00383-8
- ISSN : 0166-218X
- DBLP ID : journals/dam/FujitoN02
- Web of Science ID : WOS:000174769500003