The integrality gap of the asymmetric travelling salesman problem

Abstract

The Asymmetric Travelling Salesman Problem (ATSP) is a famous problem in the field of Combinatorial Optimization with many applications in industry. This problem is known to be NP-hard; moreover, no constant factor polytime approximation algorithm is known for solving the ATSP even when the costs are metric. In this thesis we study the integrality gap for the ATSP, i.e. the worst-case ratio between the ATSP and its linear programming relaxation ATSPLP. The ATSPLP provides a lower bound for the ATSP, which is useful for branch and bound solution techniques as well as for providing a proof of the quality of heuristic solutions. The integrality gap gives a measure of the "goodness" of this lower bound; moreover, a constructive proof showing this integrality gap is at most some constant alpha would provide an alpha-approximation algorithm for the ATSP. It is not known whether the integrality gap for the ATSP and the ATSPLP is even bounded. This contrasts sharply with the symmetric case with metric costs where a 32 -approximation algorithm is known and the integrality gap has been shown to be at most 3/2. It was conjectured that the integrality gap for the asymmetric case was 4/3. In this thesis, we refute this claim. We compute the integrality gap exactly for 4 ≤ n ≤ 7 and provide some partial results for 8 ≤ n ≤ 15. We also provide two infinite families of extreme points of the polytope associated with the ATSPLP, the Asymmetric Subtour Elimination Polytope (ASEP), whose integrality gaps approach 3/2 and 2 respectively. Throughout this thesis, we explore several different properties of the extreme points of the ASEP. We provide two operations which can be used to create new extreme points. We also present an algorithm that can generate almost all of the extreme points of the ASEP for 4 ≤ n ≤ 7 much more quickly than other polyhedral extreme point enumeration algorithms. We explore the facets of the ATSP-polytope and use them to further investigate the integrality gap. We finish this thesis with an exploration of the Strongly Connected Spanning Subgraph Problem (a close relative of the ATSP) and explore how much we can relax the ATSP and still have a hope of having a lower bound on the optimal value.