A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem
A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem
复制标题
加权边支配集问题推广的 2 1/10 近似算法
DOI：
10.1007/3-540-45253-2_13
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Ojas D. Parekh
中科院分区：
文献类型：
--
作者：
R. Carr;Toshihiro Fujito;G. Konjevod;Ojas D. Parekh
我们研究加权边缘式设置问题的近似性。尽管即使是未加权的情况也是NP完整的，但在这种情况下，大小的解决方案最多可以有效地计算出最小值，这是由于其与最小最大匹配的密切关系。但是，在加权情况下，这种良好的关系不存在。在本文中，在表明加权边缘统治与经过良好研究的加权顶点覆盖问题一样难以近似之后，我们考虑了一种自然策略，将边缘式的设置减少到边缘盖。我们的主要结果是一种简单的2 1/10-适当的算法，用于加权边缘主体设置问题，改善了现有比率，因为简单地减少了加权顶点覆盖率，即2RWVC，其中RWVC是任何多项式 - 近似值的保证时间加权顶点覆盖算法。 RWVC当前的最佳值位于2-log Log | V |/2日志| V |。此外，我们确定2 1/10的因素是紧密的，因为它与自然线性编程的放松所产生的完整性差距相吻合。
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 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 2rWVC, where rWVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of rWVC currently stands 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 incurred by a natural linear programming relaxation of the problem.