Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem

DOI10.1287/opre.28.3.623zbMath0442.90069OpenAlexW2033053473MaRDI QIDQ3885528

Roy Jonker, J. A. van der Velde, A. Volgenant, G. de Leve

Publication date: 1980

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.28.3.623

zbMATH Keywords

distance matrixequivalent problem transformationcalculation of lower boundsasymmetric assignment problemassignment relaxationassignment algorithmssymmetric traveling salesman problems

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items

Improving Christofides' lower bound for the traveling salesman problem, The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching, A symmetry-free polynomial formulation of the capacitated vehicle routing problem, A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program, Better assignment lower bounds for the Euclidean traveling salesman problem, Solving symmetric vehicle routing problems asymmetrically, Lower bounds for symmetricK-peripatetic salesman problems, On dual solutions of the linear assignment problem, An improved assignment lower bound for the Euclidean traveling salesman problem