Volume 4 (2008) Article 9 pp. 191-193 [COMMENT]

On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem

by Viswanath Nagarajan

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
DOI: 10.4086/toc.2008.v004a009

Download article from ToC site:
[PS (137K)]    [PS.GZ (48K)]    [PS.ZIP (48K)]
[PDF (118K)]    [DVI (17K)]    [ZIP (24K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
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 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.