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

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.