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.