Abstract
Let G = (V ; E) be an undirected graph. Given an odd number k = 2l + 1, a matching M is said to be k-optimal if it does not admit an augmenting path of length less than or equal to k. We prove jMj jM j(l+ 1)=(l+ 2), where M is a maximum cardinality matching. If M is not already (k + 2)-optimal, using M, in O(jEj) time we compute a (k + 2)-optimal matching. We show that starting with any matching, repeated k-optimizations result in an optimal matching in O( p jM jjEj) time. This approximation scheme extends to the minimum weight perfect matching, and the minimum weight uncapacitated perfect 2-matching problems over complete graphs, and complete bipartite graphs with edge weights of one and two. In particular, we obtain a fast approximation algorithm for the traveling salesman problem over complete graphs with edge weights of one and two.