Improving Christofides' lower bound for the traveling salesman problem

DOI10.1080/02331938508843068zbMath0577.90084MaRDI QIDQ3698662

A. Volgenant, Roy Jonker

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 salesman; lower bound; complete cycle problem; identification of non-optimal edges

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C35: Extremal problems in graph theory

65K05: Numerical mathematical programming methods

90C10: Integer programming

Related Items

A note on dual solutions of the assignment problem in connection with the traveling salesman problem, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, Better assignment lower bounds for the Euclidean 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