Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem

DOI10.1016/0167-6377(89)90047-3zbMath1418.90214OpenAlexW2037698052MaRDI QIDQ2314406

Michelangelo Grigni, Dimitris J. Bertsimas

Publication date: 22 July 2019

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

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90047-3

zbMATH Keywords

traveling salesman problemspacefilling curve heuristic

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

Further results on the probabilistic traveling salesman problem ⋮ Genetically improved presequences for Euclidean traveling salesman problems ⋮ Assouad-Nagata dimension and gap for ordered metric spaces ⋮ Universal Algorithms for Clustering Problems ⋮ Spaces that can be ordered effectively: virtually free groups and hyperbolicity ⋮ Algorithms for the universal and a priori TSP ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Efficacy of spacefilling heuristics in Euclidean combinatorial optimization

Cites Work

• Unnamed Item
• An O(N log N) planar travelling salesman heuristic based on spacefilling curves
• Spacefilling curves and the planar travelling salesman problem
• Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space