The quadratic travelling salesman problem: complexity and approximation

In this thesis we study the Quadratic Travelling Salesman Problem (QTSP) which generalizes the well-studied Traveling Salesman Problem and several of its variations. QTSP is to find a least cost Hamiltonian cycle in an edge-weighted graph, where costs are defined for all pairs of edges contained in the Hamilton cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the adjacent quadratic TSP, which only considers costs for pairs of adjacent edges. We give a complete characterization of the QTSP linearization problem and give a polynomial time algorithm to find a linearization whenever one exists. The fixed-rank QTSP is introduced as a restricted version of the QTSP where the cost matrix has fixed rank p. We study QTSP by examining the complexity of searching exponential neighbourhoods for QTSP, the fixed-rank QTSP and the adjacent quadratic TSP. We develop pseudopolynomial time algorithms for many of these special cases, and give FPTAS whenever possible. Polynomial algorithms are given for each special case which is not NP-hard.