For NP-hard problems, it is often useful to study relaxations that are easier to solve. In the previous chapter, we already saw two approximation algorithms that started by solving a relaxation: finding a minimum-cost connected spanning subgraph in Christofides’ algorithm and finding a minimum-cost cycle cover in the cycle cover algorithm.

Another kind of relaxation arises by formulating the problem as an integer linear program and dropping the integrality constraints. In this chapter, we will study such linear programming relaxations for Symmetric TSP with Triangle Inequality and Symmetric TSP. These two equivalent versions of the problem give rise to two linear programming relaxations, which turn out to be equivalent as well (by the splitting-off technique). We also study polyhedral descriptions of connectors and T-joins and the integrality ratio of the subtour LP.