In which we describe a -approximate algorithm for the Metric TSP, we introduce the Set Cover problem, observe that it can be seen as a more general version of the Vertex Cover problem, and we devise a logarithmic-factor approximation algorithm.
1. Better Approximation of the Traveling Salesman Problem
In the last lecture we discussed equivalent formulations of the Traveling Salesman problem, and noted that Metric TSP-R can also be seen as the following problem: given a set of points and a symmetric distance function that satisfies the triangle inequality, find a multi-set of edges such that is a connected multi-graph in which every vertex has even degree and such that is minimized.
Our idea will be to construct by starting from a minimum-cost spanning tree of , and then adding edges so that every vertex becomes of even degree.
But how do we choose which edges to add to ?
In which we prove the equivalence of three versions of the Traveling Salesman Problem, we provide a 2-approximate algorithm, we review the notion of Eulerian cycle, we think of the TSP as the problem of finding a minimum-cost connected Eulerian graph, and we revisit the 2-approximate algorithm from this perspective.
1. Variations of the Traveling Salesman Problem
Recall that an input of the Traveling Salesman Problem is a set of points and a non-negative, symmetric, distance function such that for every .
The goal is to find a cycle that reaches every vertex and that has minimal total length .
There are different versions of this problem depending on whether we require to satisfy the triangle inequality or not, and whether we allow the loop to pass through the same point more than once.
- General TSP without repetitions (General TSP-NR): we allow arbitrary symmetric distance functions, and we require the solution to be a cycle that contains every point exactly once;
- General TSP with repetitions (General TSP-R): we allow arbitrary symmetric distance functions, and we allow all cycles as an admissible solution, even those that contain some point more than once;
- Metric TSP without repetitions (Metric TSP-NR): we only allow inputs in which the distance function satisfies the triangle inequality, that is
and we only allow solutions in which each point is reached exactly once;
- Metric TSP with repetitions (Metric TSP-R): we only allow inputs in which the distance function satisfies the triangle inequality, and we allow all cycles as admissible solutions, even those that contain some point more than once.