Approximation Algorithms for the Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is probably one of the best-studied problems in discrete optimization. Given a complete weighted graph with n vertices, the task is to find a tour of minimal length that visits every vertex exactly once. In this thesis we will focus on two questions regarding the traveling salesman problem: Finding the approximation ratio of the k-Opt and Lin-Kernighan algorithm and the integrality ratio of the subtour LP. <br /> The k-Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in each step to get a shorter tour. In the first part of the thesis we determine the exact approximation ratio v(n/2) for the 2-Opt algorithm. Then we show that for any fixed k>=3 the approximation ratio of the k-Opt algorithm for Metric TSP is O(n^{1/k}). Assuming the Erdos girth conjecture, we prove a matching lower bound of O(n^{1/k}). Unconditionally, we obtain matching bounds for k=3,4,6 and a lower bound of O(n^{2/(3k-3)}). Our most general bounds depend on the values of a function from extremal graph theory and are tight up to a factor logarithmic in the number of vertices unconditionally. Moreover, all the upper bounds also apply to a parameterized version of the Lin-Kernighan algorithm with appropriate parameters. Furthermore, we show that the approximation ratio of k-Opt for Graph TSP is between O(log(n)/loglog(n)) and O({log(n)/loglog(n)}^{log_2(9)+e}) for all e>0. If the vertices of the instance can be embedded into R^d such that the distances arise from the p-norm, we show that the approximation ratio is O(log(n)/loglog(n)). For the (1,2)-TSP we prove that the exact approximation ratio of the 3-Opt algorithm is 11/8. We introduce a modified version of the k-Opt algorithm for the (1,2)-TSP and show that it has for k=3 an exact approximation ratio of 4/3. The k-improv algorithm is the currently best approximation algorithm with respect to approximation ratio for the (1,2)-TSP. We give a lower bound of 11/10 for the k-improv algorithm for arbitrarily fixed k. This lower bound also carries over to the k-Opt algorithm for the (1,2)-TSP. <br /> Another useful tool to approximate the TSP is the subtour LP. Many approximation algorithms use the optimal solution of the well-known LP relaxation. Although the exact integrality ratio of the subtour LP is still unknown, it is conjectured to be 4/3. In the second part of the thesis we compute the exact integrality ratio for Rectilinear TSP with up to 10 vertices. Based on the computation results we give lower bounds depending on the number of vertices for several TSP variants and show that some of them are tight under certain assumptions. We also investigate the concept of local optimality with respect to integrality ratio and develop several algorithms to find instances with high integrality ratio for Euclidean TSP. <br /> Moreover, we improve the upper bound on the integrality ratio for s-t Path TSP to 1.5273.