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

DOI10.1016/S0022-0000(76)80016-5MaRDI QIDQ1226033zbMATH OpenFDO

Authors K. Appert

Publication date 1976

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

Full work available at URL https://doi.org/10.1016/S0022-0000(76)80016-5

Mathematics Subject Classification ID

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

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A method for solving traveling-salesman problems
• A Note on the Efficiency of Hashing Functions
• Computer Solutions of the Traveling Salesman Problem
• Discrete Optimizing
• scientific article; zbMATH DE number 3264644 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling Salesman Problem: A Survey
• The traveling-salesman problem

Cited in

(10)

• The optimum assignments and a new heuristic approach for the traveling salesman problem
• Discrete extremal problems
• Genetic algorithms and traveling salesman problems
• Data-independent neighborhood functions and strict local optima
• Polynomial transformations and data-independent neighborhood functions
• An analysis of neighborhood functions on generic solution spaces
• On the relative complexity of 15 problems related to~0/1-integer programming
• The traveling salesman problem: An update of research
• The adjacency relation on the traveling salesman polytope is NP-Complete
• A normal fan projection algorithm for low-rank optimization

This page was built for publication: Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient

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