CS261 Lecture 4: TSP and Set Cover

In which we describe a {1.5}-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 {X} and a symmetric distance function {d: X \times X \rightarrow {\mathbb R}_{\geq 0}} that satisfies the triangle inequality, find a multi-set of edges such that {(X,E)} is a connected multi-graph in which every vertex has even degree and such that {\sum_{(u,v)\in E} d(u,v)} is minimized.

Our idea will be to construct {E} by starting from a minimum-cost spanning tree of {X}, and then adding edges so that every vertex becomes of even degree.

But how do we choose which edges to add to {T}?

Continue reading