Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient

DOI10.1016/S0022-0000(76)80016-5zbMath0326.90040MaRDI QIDQ1226033

K. Appert

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Algorithms in computer science (68W99)

Related Items

Polynomial transformations and data-independent neighborhood functions, Discrete extremal problems, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, An analysis of neighborhood functions on generic solution spaces, Data-independent neighborhood functions and strict local optima, The adjacency relation on the traveling salesman polytope is NP-Complete, Genetic algorithms and traveling salesman problems, The optimum assignments and a new heuristic approach for the traveling salesman problem, The traveling salesman problem: An update of research

Cites Work

• Unnamed Item
• Unnamed Item
• A Dynamic Programming Approach to Sequencing Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem
• A Method for Solving Traveling-Salesman Problems
• Computer Solutions of the Traveling Salesman Problem
• Discrete Optimizing
• The Traveling Salesman Problem: A Survey
• A Note on the Efficiency of Hashing Functions