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)
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
Published: February 17, 2008
Keywords: combinatorial optimization, LP relaxation, traveling salesman path
Categories: comment, algorithms, approximation algorithms, combinatorial optimization, graphs, traveling salesman, LP relaxation
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.
Licensed under a Creative Commons License