We study the approximability of the weighted edge-dominating set problem. A
lthough 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 clos
e relationship with minimum maximal matching; however, in the weighted case
such a nice relationship is not known to exist. In this paper, after showi
ng that weighted edge domination is as hard to approximate as the well stud
ied weighted vertex cover problem, we consider a natural strategy, reducing
edge-dominating set to edge cover. Our main result is a simple 2 1/10-appr
oximation 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-tim
e weighted vertex cover algorithm. The best value of r(WVC) currently stand
s at 2-log log |V|/2 log |V|. Furthermore we establish that the factor of 2
1/10 is tight in the sense that it coincides with the integrality gap incu
rred by a natural linear programming relaxation of the problem.