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

DOI10.1137/S0097539793251244zbMath0936.68052MaRDI 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 algorithms; graph algorithms; explicit machine computation and programs (in computer science heading); explicit machine computation and programs (in optimization heading)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

49-04: Software, source code, etc. for problems pertaining to calculus of variations and optimal control

68-04: Software, source code, etc. for problems pertaining to computer science

Related Items

Improving TSP Tours Using Dynamic Programming over Tree Decompositions., Unnamed Item, 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, Random shortest paths: non-Euclidean instances for metric optimization problems, Average-case approximation ratio of the 2-opt algorithm for the TSP, Analysis of random restart and iterated improvement for global optimization with application to the traveling salesman problem, Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, The simultaneous semi-random model for TSP, A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem, Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem, On the Complexity of Local Search in Unconstrained Quadratic Binary Optimization, Nonoblivious 2-Opt heuristics for the traveling salesman problem, Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic, Smoothed Analysis of Local Search Algorithms, The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension