Home | Business News | Browse by Publication | M | Mathematics of Operations Research

On the integrality ratio for the asymmetric traveling salesman problem.

Article Excerpt
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 MSC2000 subject classification: Primary: 05C85, 68W25, 90C27, 90C59; secondary: 05C45, 68R05, 68R10, 68W40, 90C05, 90C10

OR/MS subject classification: Primary: networks/graphs--traveling salesman; secondary: analysis of algorithms--suboptimal algorithms; integer programming--theory

1. Introduction. The traveling salesman problem (TSP)--the problem of finding a minimum cost tour through a set of cities--is the most celebrated combinatorial optimization problem. It is often used as a testbed for novel ideas, as was the case for Adleman's molecular computing (Adleman [1]), memetic algorithms (Moscato [23]), or ant colony optimization (Dorigo et al. [10]), to cite just a few examples. The TSP book (Lawler et al. [20]) provides a tour d'horizon of combinatorial optimization, illustrating all the concepts and techniques on the TSP.

The traveling salesman problem comes in two variants. The symmetric version (STSP) assumes that the cost [c.sub.ij] of going from city i to city j is equal to [c.sub.ji] while the more general asymmetric version (ATSP) does not make this assumption. In both cases, it is usually assumed--and we make this assumption in the rest of this paper--that we are in the metric case, i.e., the costs satisfy the triangle inequality: [c.sub.ij] + [c.sub.jk] [greater than or equal to] [c.sub.ik] for all i, j, k. Even though the TSP is the most studied combinatorial optimization problem, little progress has been made on its approximability in the general metric case in the last quarter of a century. Christofides in 1976 (Christofides [9]) discovered a 3/2-approximation algorithm (1) for STSP. No better approximation algorithm has since been found for the general symmetric metric case. (For the special case of Euclidean instances, Arora [3] and Mitchell [21] found polynomial-time approximation schemes.) For the asymmetric case, no constant approximation algorithm is known. Frieze et al. [11] gave a simple [log.sub.2](n)-approximation algorithm for ATSP in 1982, where n is the number of vertices. In the last two years, this was slightly improved to a guarantee of 0.999[log.sub.2](n) by Blaser [4] and subsequently to 4/3 [log.sub.3](n) [approximately equal to] 0.8412 [log.sub.2](n) by Kaplan et al. [19]. This is in sharp contrast to the best inapproximability result of Papadimitriou and Vempala [24] which shows the nonexistence of an [alpha]-approximation algorithm for ATSP for [alpha] = 117/116 - [??] and for STSP for [alpha] = 220/219 - [??], unless P = NP. Whether ATSP can be approximated within a constant factor is a major open question, and so is whether an [alpha]-approximation algorithm for STSP can be obtained for a constant [alpha] < [3/2].

Mathematical programming relaxations and especially linear programming relaxations have played a central role both in solving combinatorial optimization problems in practice (see, e.g., Applegate et al.'s [2] record exact solution of the STSP instance having all 24,978 cities in Sweden) and in the design and analysis of approximation algorithms. For the traveling salesman problem, Held and Karp [13, 14] introduced a linear programming relaxation for both the symmetric and asymmetric versions and gave several equivalent formulations for them. The bound they gave is often referred to as the Held-Karp lower bound. It can be computed in polynomial time and very efficiently in practice. As a linear program, this Held-Karp relaxation can be formulated for the symmetric case by writing the cut constraints and the degree constraints: (2)

min [summation over (e [member of] E)] [c.sub.e][x.sub.e]

subject to x([delta](S)) [greater than or equal to] 2, for all [empty set] [not equal to] S [not equal to] V, x([delta](v)) = 2, for all v [member of] V, [less than or equal to] [x.sub.e] [less than or equal to] 1, for all e [member of] E, (1)

and in the asymmetric case by writing the cut constraints and the in-degree and out-degree constraints: (3)

min [summation over (e [member of] E)] [c.sub.e][x.sub.e]

subject to x([[delta].sup.+](S)) [greater than or equal to] 1, for all [empty set] [not equal to] S [not equal to] V,

x([[delta].sup.+](v)) = 1, for all v [member of] V,

x([[delta].sup.-](v)) = 1, for all v [member of] V,

[less than or equal to] [x.sub.e] [less than or equal to] 1, for all e [member of] E.

One can easily see that the asymmetric formulation is equivalent to the symmetric one for the special case of symmetric costs and, therefore, it makes sense to denote by HK the Held-Karp bound both in the symmetric and asymmetric cases.

The quality of the Held-Karp lower bound has puzzled researchers for over 25 years. Wolsey [27] and later Shmoys and Williamson [25] showed that for symmetric (metric) instances we have STSP [less than or equal to] [3/2] HK, where STSP denotes the optimum value of an STSP instance. This was shown by proving that the tour returned by Christofides' [9] heuristic has cost bounded above by 3/2 HK. For ATSP, Williamson [26] showed that the Frieze et al. [11] heuristic returns a tour of cost at most...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!