Comments, updates
A Comment on the LP Relaxation for the Asymmetric Traveling Salesman Path Problem
by Viswanath Nagarajan
Tepper School of Business,
Carnegie Mellon University
Email: viswa[ta]cmu[tod]edu
Received: January 2, 2008
Published: February 17, 2008
We observe that the LP relaxation for the Asymmetric Traveling Salesman Path Problem suggested in Section 5 of the paper "An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem" by Chekuri and Pál is not accurate, and state a corrected linear relaxation for the problem. The inaccuracy occurs in the statement of an open problem, and does not affect the validity of any of the results in the paper.