Technical Note—Bounds for the Travelling-Salesman Problem

DOI10.1287/OPRE.20.5.1044zbMath0251.90027OpenAlexW2028046799MaRDI QIDQ5665016

Nicos Christofides

Publication date: 1972

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

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

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (14)

Improving Christofides' lower bound for the traveling salesman problem ⋮ Generalized travelling salesman problem through n sets of nodes: The asymmetrical case ⋮ Bi-objective data gathering path planning for vehicles with bounded curvature ⋮ Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem ⋮ A branch-and-bound approach for a vehicle routing problem with customer costs ⋮ 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 ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ Principal component analysis for evaluating the feasibility of cellular manufacturing without initial machine-part matrix clustering ⋮ Bounds for 3-matroid intersection problems ⋮ Cluster based branching for the asymmetric traveling salesman problem ⋮ On dual solutions of the linear assignment problem ⋮ A restricted Lagrangean approach to the traveling salesman problem ⋮ On the refinement of bounds of heuristic algorithms for the traveling salesman problem

This page was built for publication: Technical Note—Bounds for the Travelling-Salesman Problem