On the Complexity of Local Search for the Traveling Salesman Problem

DOI10.1137/0206005zbMath0381.68043OpenAlexW2055370404MaRDI QIDQ4162482

Kenneth Steiglitz, Christos H. Papadimitriou

Publication date: 1977

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Algorithms in computer science (68W99)

Related Items

On the number of iterations of local improvement algorithms, Optimization and optimality test for the Max-Cut Problem, Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, On the power of neural networks for solving hard problems, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, Local search: is brute-force avoidable?, On minimal Eulerian graphs, Searching for better fill-in, Traveling salesman problem and local search, The adjacency relation on the traveling salesman polytope is NP-Complete, The Euclidean traveling salesman problem is NP-complete, On the depth of combinatorial optimization problems, Pairs of Adjacent Hamiltonian Circuits with Small Intersection, Heuristic methods and applications: A categorized survey, The optimum assignments and a new heuristic approach for the traveling salesman problem, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS