  We present a framework for approximating the metric TSP based on a novel use
of matchings. Traditionally, matchings have been used to add edges in order to
make a given graph Eulerian, whereas our approach also allows for the removal
of certain edges leading to a decreased cost.
  For the TSP on graphic metrics (graph-TSP), the approach yields a
1.461-approximation algorithm with respect to the Held-Karp lower bound. For
graph-TSP restricted to a class of graphs that contains degree three bounded
and claw-free graphs, we show that the integrality gap of the Held-Karp
relaxation matches the conjectured ratio 4/3. The framework allows for
generalizations in a natural way and also leads to a 1.586-approximation
algorithm for the traveling salesman path problem on graphic metrics where the
start and end vertices are prespecified.
