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

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

DOI: 10.4086/toc.2008.v004a009
© 2008 Viswanath Nagarajan
Creative Commons License Licensed under a Creative Commons License