×

zbMATH — the first resource for mathematics

On the refinement of bounds of heuristic algorithms for the traveling salesman problem. (English) Zbl 0564.90040
A number of heuristics for the traveling salesman problem (TSP) rely on the assumption that the triangle inequality (TI) is satisfied. When TI does not hold, the paper proposes a transformation such that for the transformed problem the TI holds. Consequently, the bounds obtained for heuristics are valid with appropriate modification. Moreover, for a TSP satisfying TI the same transformation strengthens such bounds. The transformation essentially maps the problem into one that is minimal with respect to the property that TI holds. For the symmetric TSP the transformation is particularly simple. For an application of the transformation in the asymmetric case we need the dual solution of an assignment problem.

MSC:
90C10 Integer programming
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A.A. Adrabinski and M.M. Syslo, ”Computational experiments with some heuristic algorithms for the traveling salesman problem”, Report No. N-78, Institute of Computer Science, University of Wrocław, 1980. · Zbl 0525.90095
[2] N. Christofides, ”Worst-case analysis of a new heuristic for the traveling salesman problem”, GSIA, Carnegie–Mellon University, 1976.
[3] N. Christofides, ”Bounds for the traveling salesman problem”,Operations Research 5 (1972) 1044–1056. · Zbl 0251.90027 · doi:10.1287/opre.20.5.1044
[4] G. Cornuejols and G.L. Nemhauser, ”Tight bounds for Christofides’ traveling salesman heuristic”. Working paper No. 7627, Center for Operations Research and Economics, Universite Catholique de Louvain (Louvain-la-Neuve, 1976). · Zbl 0396.90098
[5] A.M. Frieze, ”Worst-case analysis of algorithms for the traveling salesman problem”, Research Report, Department of Computer Science, University of London, 1978.
[6] M. Held and R.M. Karp, ”The traveling salesman problem and minimum spanning trees”,Operations Research 18 (1970) 1138–1162. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[7] M. Held and R.M. Karp, ”A dynamic programming approach to sequencing problems”,Journal of the Society for Industrial and Applied Mathematics 10 (1962) 196–210. · Zbl 0106.14103 · doi:10.1137/0110015
[8] S. Lin and B.W. Kernighan, ”An effective heuristic for the traveling salesman problem”,Operations Research 21 (1973) 498–516. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[9] C.H. Papadimitriou and K. Steiglitz, ”Some examples of difficult traveling salesman problems”,Operations Research 26 (1978) 434–443. · Zbl 0383.90105 · doi:10.1287/opre.26.3.434
[10] D.J. Rosenkrantz, R.E. Stearns and P.M. Lewis, ”An analysis of several heuristics for the traveling salesman problem”,SIAM Journal on Computing 6 (1977) 563–581. · Zbl 0364.90104 · doi:10.1137/0206041
[11] S. Sahni and T. Gonzales, ”P-complete approximation problems”,Journal of the ACM 23 (1976) 555–565. · Zbl 0348.90152 · doi:10.1145/321958.321975
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.