On the Complexity of Local Search for the Traveling Salesman Problem
From MaRDI portal
Publication:4162482
DOI10.1137/0206005zbMath0381.68043MaRDI QIDQ4162482
Christos H. Papadimitriou, Kenneth Steiglitz
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
68Q25: Analysis of algorithms and problem complexity
90B10: Deterministic network models in operations research
68W99: Algorithms in computer science
Related Items
On the number of iterations of local improvement algorithms, On the power of neural networks for solving hard problems, 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, 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