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

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.

Continue reading