Traveling salesman problem and local search

DOI10.1016/0893-9659(92)90090-VMaRDI QIDQ1195657zbMATH OpenFDO

Authors Bruno Codenotti, Luciano Margara

Publication date 6 January 1993

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

Full work available at URL https://doi.org/10.1016/0893-9659(92)90090-V

zbMATH Keywords

difference equationlocal search heuristicsNP-completetraveling salesman

Mathematics Subject Classification ID

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

Recommendations

• Local search and the local structure of NP-complete problems
• Theoretical aspects of local search.
• Local search structure in the symmetric travelling salesperson problem under a general class of rearrangement neighborhoods
• scientific article; zbMATH DE number 177832
• Efficiency of a local algorithm for solving the traveling salesman problem

Cites work

• How easy is local search?
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• 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
• The complexity of optimization problems
• Traveling salesman problem and local search

Cited in

(19)

• Some additional properties of elementary landscapes
• Traveling salesman problem and local search
• Local search and the local structure of NP-complete problems
• On the quality of local search for the quadratic assignment problem
• The theory of elementary landscapes
• Weakly symmetric graphs, elementary landscapes, and the TSP
• Linearity in the traveling salesman problem
• Using group theory and transition matrices to study a class of metaheuristic neighborhoods
• Extended neighborhood: Definition and characterization
• Routing problems: A bibliography
• On the classification of NP-complete problems in terms of their correlation coefficient
• The parameterized complexity of local search for TSP, more refined
• Travelling Salesman with a Self-Similar Itinerary
• The parameterized complexity of local search for TSP, more refined
• Neutrality in fitness landscapes.
• Local search structure in the symmetric travelling salesperson problem under a general class of rearrangement neighborhoods
• Elementary landscape decomposition of the frequency assignment problem
• Quasiabelian landscapes of the traveling salesman problem are elementary
• Efficiency of a local algorithm for solving the traveling salesman problem

This page was built for publication: Traveling salesman problem and local search

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