A $${{10}}$$ -Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

Robert Carr (), Toshihiro Fujito (), Goran Konjevod () and Ojas Parekh ()
Additional contact information
Robert Carr: Sandia National Laboratory
Toshihiro Fujito: Nagoya University Furo
Goran Konjevod: Carnegie Mellon University
Ojas Parekh: Carnegie Mellon University

Journal of Combinatorial Optimization, 2001, vol. 5, issue 3, No 4, 317-326

Abstract: Abstract We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple $$2\frac{1}{{10}}$$ -approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r WVC, where r WVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r WVC currently stands at $$2 - \frac{{\log \log \left| V \right|}}{{2\log \left| V \right|}}$$ . Furthermore we establish that the factor of $$2\frac{1}{{10}}$$ is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.

Keywords: approximation algorithm; edge-dominating set; vertex cover; edge cover (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1011445210568 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:3:d:10.1023_a:1011445210568

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011445210568

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().