# 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}$?

# CS261 Lecture 3: TSP and Eulerian Cycles

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 ${X}$ and a non-negative, symmetric, distance function ${d:X \times X \rightarrow {\mathbb R}}$ such that ${d(x,y) = d(y,x) \geq 0}$ for every ${x,y\in X}$.

The goal is to find a cycle ${C=v_0\rightarrow v_1 \rightarrow v_2 \rightarrow \cdots v_{m-1} \rightarrow v_m = v_0}$ that reaches every vertex and that has minimal total length ${cost_d(C) := \sum_{i=0}^{m-1} d(v_i,v_{i+1})}$.

There are different versions of this problem depending on whether we require ${d(\cdot,\cdot)}$ to satisfy the triangle inequality or not, and whether we allow the loop to pass through the same point more than once.

1. 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;
2. 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;
3. Metric TSP without repetitions (Metric TSP-NR): we only allow inputs in which the distance function ${d(\cdot,\cdot)}$ satisfies the triangle inequality, that is

$\displaystyle \forall x,y,z \in X.\ d(x,z) \leq d(x,y) + d(y,z)$

and we only allow solutions in which each point is reached exactly once;

4. 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.