New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
From MaRDI portal
Publication:4268854
DOI10.1137/S0097539793251244zbMath0936.68052MaRDI QIDQ4268854
Craig A. Tovey, Howard J. Karloff, Barun Chandra
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
analysis of algorithms; graph algorithms; explicit machine computation and programs (in computer science heading); explicit machine computation and programs (in optimization heading)
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
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, 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, 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
