This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Charikar, M. Articles by Karloff, H. Search for Related Content

On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

Department of Computer Science, Princeton University, 35 Olden Street, Princeton, New Jersey 08540, USA
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA
AT&T Labs—Research, 180 Park Avenue, Florham Park, New Jersey 07932, USA
moses{at}cs.princeton.edu
goemans{at}math.mit.edu
howard{at}research.att.com

We improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2.

Key Words: asymmetric traveling salesman problem; Held-Karp relaxation; integrality ratio; approximation algorithm; ATSP
History: Received: January 4, 2005; revision received: November 15, 2005;

This article has been cited by other articles:

				G. Benoit and S. Boyd Finding the Exact Integrality Gap for Small Traveling Salesman Problems Mathematics of Operations Research, November 1, 2008; 33(4): 921 - 931. [Abstract] [PDF]