Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit

DOI10.1287/OPRE.28.5.1219zbMath0449.90093OpenAlexW2148893547MaRDI QIDQ3896864

Roy Jonker, Rob Kaas, Ton Volgenant

Publication date: 1980

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

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

zbMATH Keywords

heuristicscomplete undirected graphweighted undirected graphdata- dependent boundsdata-independent boundsminimum weight Hamiltonian circuit problem

Mathematics Subject Classification ID

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

Related Items (6)

Improving Christofides' lower bound for the traveling salesman problem ⋮ Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem ⋮ Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem ⋮ A note on the approximation of the asymmetric traveling salesman problem. ⋮ Identification of non-optimal arcs for the traveling salesman problem ⋮ Heuristic methods and applications: A categorized survey

This page was built for publication: Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit