On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs
Author
Fast, Caleb
Date
2014-04-11Advisor
Hicks, Illya V.
Degree
Master of Arts
Abstract
This thesis provides new bounds on the strength of the subtour relaxation of the
Traveling Salesman Problem (TSP) for fractional 2-matching cost instances whose
support graphs have no fractional cycles larger than five vertices. This work provides
insight for improving approximation heuristics for the TSP and into the structure
of solutions produced by the subtour relaxation. Guided by a T-join derived from
the subtour relaxation, I form a tour by adding edges to the subtour relaxation. By
this constructive process, I prove that the optimal solution of the TSP is within 4/3,
17/12, or strictly less than 3/2 of the optimal solution of the subtour relaxation.
Thus, this thesis takes a step towards proving the 4/3 conjecture for the TSP and
the development of a 4/3 approximation algorithm for the TSP. These developments
would provide improved approximations for applications such as DNA sequencing,
route planning, and circuit board testing.