| Article ID: | iaor201110072 |
| Volume: | 8 |
| Issue: | 4 |
| Start Page Number: | 525 |
| End Page Number: | 539 |
| Publication Date: | Nov 2011 |
| Journal: | Discrete Optimization |
| Authors: | Carr Robert, Boyd Sylvia |
| Keywords: | graphs |
Consider the traveling salesman problem (TSP) defined on the complete graph, where the edge costs satisfy the triangle inequality. Let TOUR denote the optimal solution value for the TSP. Two well‐known relaxations of the TSP are the subtour elimination problem and the 2‐matching problem. If we let SUBT and 2M represent the optimal solution values for these two relaxations, then it has been conjectured that TOUR/SUBT ≤ 4/3, and that 2M/SUBT ≤10/9.