Résumé | 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.
This is joint work with Ola Svensson. |