New Approximation Algorithms for Minimum Weighted Edge Cover
S M Ferdous, Arif Khan, Alex Pothen, "New Approximation Algorithms for Minimum Weighted Edge Cover." In the proceedings of 2018 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, 2018.
Abstract: We describe two new 3/2-approximation algorithms and a new 2-approximation algorithm for the minimum weight edge cover problem in graphs. We show that one of the 3/2-approximation algorithms, the Dual Cover algorithm, computes the lowest weight edge cover relative to previously known algorithms as well as the new algorithms reported here. The Dual Cover algorithm can also be implemented to be faster than the other 3/2-approximation algorithms on serial computers. Many of these algorithms can be extended to solve the b-Edge Cover problem as well. We show the relation of these algorithms to the K-Nearest Neighbor graph construction in semi-supervised learning and other applications.