| Article ID: | iaor1989704 |
| Country: | Netherlands |
| Volume: | 8 |
| Issue: | 2 |
| Start Page Number: | 77 |
| End Page Number: | 78 |
| Publication Date: | Apr 1989 |
| Journal: | Operations Research Letters |
| Authors: | Chvtal V. |
| Keywords: | programming: travelling salesman |
The paper observes that (i) the problem of recognizing instances of the traveling salesman problem for which the subtour relaxation has an integer optimal solution is NP-complete and (ii) there is no nontrivial upper bound on the ‘relative error’ with which the optimal value of the TSP is approximated by the optimal value of its subtour relaxation.