On the Complexity of Local Search for the Traveling Salesman Problem

DOI10.1137/0206005MaRDI QIDQ4162482zbMATH OpenOpenAlexFDO

Authors Ken Steiglitz, Christos 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) Algorithms in computer science (68W99) Deterministic network models in operations research (90B10)

Cited in

(16)

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

This page was built for publication: On the Complexity of Local Search for the Traveling Salesman Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4162482)