The traveling salesman problem and the subtour linear programming

Abstract

A salesman wishes to make a journey, visiting each of $n$ cities exactly once and finishing at the city he starts from. Suppose that there is a cost to travel from one city to another. The {\em traveling salesman problem} (TSP) is to find a journey with minimum total cost. This problem arises in a rich variety of applications, and hence has been subject of extensive research. As the recognition version of TSP is $NP$-hard, there is no polynomial time algorithm for solving it exactly unless $NP=P$. One approach to getting around the $NP$-hardness is to find {\em near-optimal} solutions. In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an {\em approximation algorithm}. \\

The TSP can be naturally formulated as an integer program involving subtour elimination constraints. Let STLP denote its linear programming relaxation, and let $\triangle$TSP denote the TSP with costs satisfying the triangle inequality. Since the optimal value of STLP provides a good lower bound on that of the TSP, the STLP has also attracted tremendous research effort. An important conjecture made by Goemans in the 1990s asserts that the optimal value of the $\triangle$TSP is bounded above by $\frac{4}{3}$ times that of the STLP. The present thesis is devoted to the study of some results on Goemans' conjecture and one of its variants. \\

In Chapter 2 it is shown that the Held-Karp bound for the STLP enjoys a certain monotonicity property, which reveals a connection between $\triangle$TSP, the subtour linear programming, and $1$-trees, and leads to a proof that the optimal value of the $\triangle$TSP is bounded above by $\frac{3}{2}$ times that of the STLP.\\

In Chapter 3 the aforementioned Goemans conjecture is proved for the graph-TSP on cubic graphs; the major technique used in the proof is to decompose a cubic graph into a cycle cover and a matching with a special structure. \\

In Chapter 4 the graph-TSP is studied in a more general setting. Using ear decomposition and a structural description, a $\frac{7}{5}$-approximation algorithm for the graph-TSP is devised, whose approximation ratio remains to be the best to date. \\

In Chapter 5 is it proved that the worst-case ratio between the values of optimal $2$-matching and optimal STLP is bounded above by $\frac{10}{9}$. Since the ratio between optimal values of the TSP and $2$-matching is bounded above by $\frac{4}{3}$, this result can help us understand the subtour linear programming deeply.