Authors Viswanath Nagarajan,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 191–193
http://theoryofcomputing.org
COMMENT
On the LP Relaxation of the Asymmetric
Traveling Salesman Path Problem
Viswanath Nagarajan
Received: January 2, 2008; published: February 17, 2008.
Abstract: 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 Com-
puting 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.
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25, 68R10, 90C59
Key words and phrases: combinatorial optimization, LP relaxation, traveling salesman path
An asymmetric metric (V, `) on vertex-set V is a function ` : V ×V → R+ that satisfies the triangle in-
equality: `(u, w) ≤ `(u, v)+`(v, w) for all u, v, w ∈ V . The Asymmetric Traveling Salesman Path Problem
(ATSPP) is defined as follows: given an n-vertex asymmetric metric (V, `) and a pair of vertices s,t ∈ V ,
find an s − t path of minimum length that visits all vertices in V . The following linear programming
relaxation for ATSPP was suggested in [1], and the authors asked whether its integrality gap is bounded
by O(log n). In the following, A denotes the set of all arcs in the complete digraph on vertex-set V , and
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2008 Viswanath Nagarajan DOI: 10.4086/toc.2008.v004a009
V ISWANATH NAGARAJAN
for any set S ⊆ V , δ − (S) = {(u, v) ∈ A | u ∈
/ S, v ∈ S} and δ + (S) = {(u, v) ∈ A | u ∈ S, v ∈
/ S}.
min ∑ `(a)x(a)
a∈A
∑ x(a) = 1 ∀v ∈ V \ {s}
a∈δ − (v)
∑ x(a) = 1 ∀v ∈ V \ {t}
a∈δ + (v)
(ATSPP-LP) ∑ x(a) ≥ 1 ∀S ⊆ V \ {s}
a∈δ − (S)
∑ x(a) ≥ 1 ∀S ⊆ V \ {t}
a∈δ + (S)
x(a) ≥ 0 ∀a ∈ A
This is clearly a relaxation of ATSPP. However, even the integer program corresponding to ATSPP-LP,
where the arc variables x(a) are constrained to be in {0, 1}, can have an optimal value that is smaller than
the optimal solution to ATSPP by a factor of Ω(n). This can be seen from the following example. The
asymmetric metric (V, `) in the example is the shortest path metric induced by the arc-weighted digraph
G in Figure 1. Graph G is defined on vertices V = {s,t, v1 , · · · , vn−2 } and arcs
E = {(vi , s) | 1 ≤ i ≤ n − 2} ∪ {(t, vi ) | 1 ≤ i ≤ n − 2} ∪ {(s,t)} ;
the length of all arcs in E \ {(s,t)} is zero and arc (s,t) has length 1.
vn−2
0 0
0 v1 0
s 0 0 t
1
Figure 1: The directed graph G in the example, with arc lengths.
It is clear that the minimum length s − t path in metric (V, `) that visits all vertices has length n − 1;
so the optimal value of the ATSPP instance is n − 1. On the other hand, setting x(a) = 1 for all a ∈ E
and x(a) = 0 otherwise, we obtain a feasible solution to ATSPP-LP; so the optimal value of the linear
program ATSPP-LP is 1. In fact, this shows that even the integer program corresponding to ATSPP-LP
has optimal value 1. In this example, the ratio of the optimal value of ATSPP to that of ATSPP-LP is
n − 1. So the integrality gap of ATSPP-LP is Ω(n).
The trouble with the linear program ATSPP-LP is that the integer program corresponding to it is not
an exact formulation of ATSPP. This can be corrected by the addition of the following two constraints
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 191–193 192
C OMMENT: LP R ELAXATION OF A SYMMETRIC T RAVELING S ALESMAN PATH P ROBLEM
to ATSPP-LP: ∑a∈δ − (s) x(a) = 0 and ∑a∈δ + (t) x(a) = 0. It is easy to see that with this modification,
the corresponding integer program is an exact formulation of ATSPP. The corrected LP relaxation is as
follows.
min ∑ `(a)x(a)
a∈A
∑ x(a) = 1 ∀v ∈ V \ {s}
a∈δ − (v)
∑ x(a) = 1 ∀v ∈ V \ {t}
a∈δ + (v)
∑ x(a) ≥ 1 ∀S ⊆ V \ {s}
a∈δ − (S)
∑ x(a) ≥ 1 ∀S ⊆ V \ {t}
a∈δ + (S)
∑ x(a) = ∑ x(a) = 0
a∈δ − (s) a∈δ + (t)
x(a) ≥ 0 ∀a ∈ A
As mentioned in Chekuri and Pál [1], it is not clear whether an augmentation lemma (similar to
Lemma 3.1 in [1]) can be proved relative to the optimal solution to such a linear program. Determining
if the integrality gap of this LP relaxation is O(log n) is an interesting open question.
References
[1] * C HANDRA C HEKURI AND M ARTIN P ÁL: An O(log n) Approximation Ratio for the Asymmetric
Traveling Salesman Path Problem. Theory of Computing, 3:197–209, 2007. [ToC:v003/a010].
AUTHOR
Viswanath Nagarajan
Tepper School of Business
Carnegie Mellon University
Tech & Frew St
Pittsburgh, PA 15213
viswa cmu edu
http://www.andrew.cmu.edu/user/viswanat
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 191–193 193