The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

DOI10.1137/0221030MaRDI QIDQ4016908zbMATH OpenOpenAlexFDO

Authors Christos Papadimitriou

Publication date 16 January 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0221030

zbMATH Keywords

local searchtravelling salesman problemPLS-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• How easy is local search?
• A modified Lin--Kernighan traveling-salesman heuristic
• Chained Lin-Kernighan for large traveling salesman problems
• scientific article; zbMATH DE number 18531
• scientific article; zbMATH DE number 177832

Cited in

(19)

• Dynamics of local search trajectory in traveling salesman problem
• On the distributed decision-making complexity of the minimum vertex cover problem
• scientific article; zbMATH DE number 2040682 (Why is no real title available?)
• On total functions, existence theorems and computational complexity
• A survey of very large-scale neighborhood search techniques
• Metaheuristics: A bibliography
• The complexity of searching implicit graphs
• A note on the complexity of local search problems
• The complexity of searching succinctly represented graphs
• Routing problems: A bibliography
• Computational aspects of the colorful Carathéodory theorem
• A new adaptive multi-start technique for combinatorial global optimizations
• A modified Lin--Kernighan traveling-salesman heuristic
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• Finding optimal subgraphs by local search
• Memetic algorithms: The polynomial local search complexity theory perspective
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

This page was built for publication: The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

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