New Results on the Old k-opt Algorithm for the Traveling Salesman Problem

DOI10.1137/S0097539793251244zbMath0936.68052OpenAlexW2079868147MaRDI QIDQ4268854

Barun Chandra, Craig A. Tovey, Howard J. Karloff

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539793251244

zbMATH Keywords

analysis of algorithmsgraph algorithmsexplicit machine computation and programs (in computer science heading)explicit machine computation and programs (in optimization heading)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Software, source code, etc. for problems pertaining to calculus of variations and optimal control (49-04) Software, source code, etc. for problems pertaining to computer science (68-04)

Related Items (18)

Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem ⋮ Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of Local Search Algorithms ⋮ The simultaneous semi-random model for TSP ⋮ The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ Unnamed Item ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem ⋮ Analysis of random restart and iterated improvement for global optimization with application to the traveling salesman problem ⋮ On the Complexity of Local Search in Unconstrained Quadratic Binary Optimization ⋮ Nonoblivious 2-Opt heuristics for the traveling salesman problem ⋮ Average-case approximation ratio of the 2-opt algorithm for the TSP ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.

This page was built for publication: New Results on the Old k-opt Algorithm for the Traveling Salesman Problem