pdf icon
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
Download article from ToC site:
[PDF (122K)]    [PS (138K)]    [PS.GZ (48K)]
[Source ZIP]
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 C. Chekuri and M. 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.