Theory of Computing
-------------------
Title : On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem
Authors : Viswanath Nagarajan
Volume : 4
Number : 9
Pages : 191-193
URL : https://theoryofcomputing.org/articles/v004a009
Abstract
--------
This is a comment on the article "An O(\log n) Approximation Ratio for
the Asymmetric Traveling Salesman Path Problem" by Chekuri and Pal,
Theory of Computing 3 (2007), 197-209. We observe that the LP relaxation for
the Asymmetric Traveling Salesman Path Problem suggested in Section 5 of that
paper 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 Chekuri - Pal paper.