Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
From MaRDI portal
Publication:3896864
DOI10.1287/opre.28.5.1219zbMath0449.90093MaRDI QIDQ3896864
Rob Kaas, Ton Volgenant, Roy Jonker
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
heuristics; complete undirected graph; weighted undirected graph; data- dependent bounds; data-independent bounds; minimum weight Hamiltonian circuit problem
90C35: Programming involving graphs or networks
05C35: Extremal problems in graph theory
65K05: Numerical mathematical programming methods
Related Items
Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, Identification of non-optimal arcs for the traveling salesman problem, A note on the approximation of the asymmetric traveling salesman problem., Heuristic methods and applications: A categorized survey, 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