Volume 4 (2008) Article 9 pp. 191-193 [COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem
A comment on:
An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem, by Chandra Chekuri and Martin Pál (ToC 3/10)
Received: January 2, 2008
Published: February 17, 2008
Keywords: combinatorial optimization, LP relaxation, traveling salesman path
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25, 68R10, 90C59

Abstract: [Plain Text Version]

This is a comment on the article "An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem" by Chekuri and Pál, 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 - Pál paper.