# zbMATH — the first resource for mathematics

Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem. (English) Zbl 0671.90085
The authors discuss the transformation of the distance matrix in the traveling salesman problem in order to use a given heuristic algorithm. Some performance bounds are derived.
Reviewer: H.T.Lau

##### MSC:
 90C35 Programming involving graphs or networks 90C10 Integer programming 90C06 Large-scale problems in mathematical programming 65K05 Numerical mathematical programming methods
Full Text:
##### References:
 [1] Burkard, R.E., Traveling salesman and assignment problems: A survey, Annals of discrete mathematics, 4, 193-215, (1979) · Zbl 0409.05041 [2] Christofides, N., Bounds for the traveling salesman problem, Operations research, 20, 1044-1056, (1972) · Zbl 0251.90027 [3] Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem, (1976), Carnegie-Mellon Univ., Pittsburgh [4] Fisher, M.L.; Nemhauser, G.L.; Wolsey, L.A., An analysis of approximations for finding a maximum weight Hamiltonian circuit, Operations research, 27, 799-809, (1979) · Zbl 0412.90070 [5] Frieze, A.M.; Galbiati, G.; Maffioli, F., On the worst-case performance of some algorithms for the asymmetric traveling salesman problem, Networks, 12, 23-39, (1982) · Zbl 0478.90070 [6] Held, M.; Karp, R.M., A dynamic programming approach to sequencing problems, SIAM journal, 10, 196-210, (1962) · Zbl 0106.14103 [7] Jeromin, B.; Körner, F., Zur verschärfung der christofides-schranke für den wert einer optimalen tour des rundreiseproblems, MOS, ser. optimization, 13, 359-371, (1982) · Zbl 0505.90051 [8] Jeromin, B.; Körner, F.; Jeromin, B.; Körner, F., On the refinement of bounds of heuristic algorithms for the traveling salesman problem, Mathematical programming, Addendum, Vol. 37, 254-117, (1987) · Zbl 0564.90040 [9] Jeromin, B.; Körner, F., Sharp bounds for Karp’s ‘patching’-algorithm for the approximate solution of the traveling salesman problem, Optimization, 17, 85-92, (1986) · Zbl 0596.90096 [10] Jeromin, B.; Körner, F., Untersuchungen über veränderungen der dualen variablen beim assignment-problem, WZ der TU Dresden, 31, 199-201, (1982) · Zbl 0483.90081 [11] Jeromin, B.; Körner, F., Some remarks on two degrees of asymmetry in the traveling salesman problem, (1987), Preprint TU Dresden [12] Jonker, R.; Kaas, R.; Volgenant, A., Data-dependent bounds for heuristics to find a minimum weight Hamiltonian circuit, Operations research, 28, 1219-1222, (1980) · Zbl 0449.90093 [13] Jonker, R.; Volgenant, A., Identification of non-optimal arcs for the traveling salesman problems, Operations research letters, 1, 85-88, (1982) · Zbl 0487.90089 [14] Jonker, R.; Volgenant, T., Transforming asymmetric into symmetric traveling salesman problems, Operations research letters, 2, 161-163, (1983) · Zbl 0529.90090 [15] Kindervater, G.; Volgenant, A.; de Leve, G.; van Gijlswijk, V., On dual solutions of the linear assignment problem, European journal of operational research, 19, 76-81, (1985) · Zbl 0557.90066 [16] Körner, F., On the degree of asymmetry in the traveling salesman problem, Zast. mat. appl. mat., 19, 117-123, (1987) · Zbl 0637.90096 [17] Körner, F., Linear transformations associated with the traveling salesman problem, (), 106-109, Teubner-Texte [18] Körner, F., On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem, European journal of operational research, 26, 262-265, (1986) · Zbl 0595.90091 [19] Körner, F., Remarks on the asymmetry in connection with the traveling salesman problem, (1987), Report · Zbl 0637.90096 [20] Korte, B., Approximative algorithms for discrete optimization problems, Annals of discrete mathematics, 4, 85-120, (1979) · Zbl 0411.90052 [21] Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., The traveling salesman problem, (1985), Wiley Chichester · Zbl 0563.90075 [22] Papadimitriou, C.; Steiglitz, K., Some examples of difficult traveling salesman problems, Operations research, 26, 434-441, (1978) · Zbl 0383.90105 [23] Schiebel, W.; Terno, J.; Unger, G., Ein beitrag zur klassifizierung von rundreiseproblemen, MOS, ser. optimization, 10, 523-528, (1979) · Zbl 0429.90049 [24] Volgenant, A.; Jonker, R., Improving christofides’ bound for the traveling salesman problem, Optimization, 16, 691-704, (1985) · Zbl 0577.90084 [25] Volgenant, A., Contributions to the solution of the traveling salesman problem and related problems, Dissertation, (1987), Amsterdam
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.