Theory of Computing, 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(logn) 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.

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 → ℝ^{+} that satisfies the triangle inequality: ℓ(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(logn). 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.

\begin{matrix}c \\ ◯ \end{matrix} 2008 Viswanath Nagarajan

Viswanath 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∈A}ℓ(a)x(a)

∑_{a∈δ^{−} (v)}x(a) = 1  ∀v ∈ V \ {s}
∑_{a∈δ^{+} (v)}x(a) = 1  ∀v ∈ V \ {t}
(ATSPP-LP) ∑_{a∈δ^{−} (S)}x(a) ≥ 1  ∀S ⊆ V \ {s}
∑_{a∈δ^{+} (S)}x(a) ≥ 1  ∀S ⊆ V \ {t}
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,v_{1},···,v_{n−2} } and arcs

E = {(v_{i},s) | 1 ≤ i ≤ n − 2} ∪ {(t,v_{i}) | 1 ≤ i ≤ n − 2} ∪ {(s,t)};

the length of all arcs in E \ {(s,t)} is zero and arc (s,t) has length 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

Comment: LP Relaxation of Asymmetric Traveling Salesman Path Problem

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∈A}ℓ(a)x(a)

∑_{a∈δ^{−} (v)}x(a) = 1  ∀v ∈ V \ {s}
∑_{a∈δ^{+} (v)}x(a) = 1  ∀v ∈ V \ {t}
∑_{a∈δ^{−} (S)}x(a) ≥ 1  ∀S ⊆ V \ {s}
∑_{a∈δ^{+} (S)}x(a) ≥ 1  ∀S ⊆ V \ {t}

∑_{a∈δ^{−} (s)} x(a) = ∑_{a∈δ^{+} (t)}x(a) = 0

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(logn) is an interesting open question.

References

[1] * Chandra Chekuri and Martin Pál: An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. Theory of Computing, 3:197–209, 2007. [ToC:v003/a010]. (document)

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