Improving Christofides' lower bound for the traveling salesman problem

DOI10.1080/02331938508843068zbMath0577.90084OpenAlexW2043988891MaRDI QIDQ3698662

Roy Jonker, A. Volgenant

Publication date: 1985

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331938508843068

zbMATH Keywords

traveling salesmanlower boundcomplete cycle problemidentification of non-optimal edges

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items

Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, Better assignment lower bounds for the Euclidean traveling salesman problem, A note on dual solutions of the assignment problem in connection with the traveling salesman problem

Cites Work

• On dual solutions of the linear assignment problem
• Identification of non-optimal arcs for the traveling salesman problem
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
• Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
• On the Relation Between the Traveling-Salesman and the Longest-Path Problems
• Computer Solutions of the Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Technical Note—Bounds for the Travelling-Salesman Problem