Traveling salesman problem and local search

DOI10.1016/0893-9659(92)90090-VzbMath0762.90078MaRDI QIDQ1195657

Bruno Codenotti, Luciano Margara

Publication date: 6 January 1993

Published in: Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

traveling salesmanNP-completedifference equationlocal search heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Quasiabelian landscapes of the traveling salesman problem are elementary ⋮ Routing problems: A bibliography ⋮ On the quality of local search for the quadratic assignment problem ⋮ On the classification of NP-complete problems in terms of their correlation coefficient ⋮ Elementary landscape decomposition of the frequency assignment problem ⋮ The theory of elementary landscapes ⋮ Weakly symmetric graphs, elementary landscapes, and the TSP ⋮ Traveling salesman problem and local search ⋮ Neutrality in fitness landscapes. ⋮ Local search structure in the symmetric travelling salesperson problem under a general class of rearrangement neighborhoods ⋮ Some additional properties of elementary landscapes ⋮ Linearity in the traveling salesman problem ⋮ Using group theory and transition matrices to study a class of metaheuristic neighborhoods

Cites Work

• Unnamed Item
• The complexity of optimization problems
• How easy is local search?
• Traveling salesman problem and local search
• Local search and the local structure of NP-complete problems
• On the Complexity of Local Search for the Traveling Salesman Problem
• Some Examples of Difficult Traveling Salesman Problems