The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
From MaRDI portal
Publication:4016908
DOI10.1137/0221030zbMATH Open0761.68048OpenAlexW2047820376MaRDI QIDQ4016908FDOQ4016908
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
Recommendations
Cited In (19)
- A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
- Finding optimal subgraphs by local search
- The complexity of gradient descent: CLS = PPAD \(\cap\) pls
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Dynamics of local search trajectory in traveling salesman problem
- Title not available (Why is that?)
- A survey of very large-scale neighborhood search techniques
- The complexity of searching implicit graphs
- On the distributed decision-making complexity of the minimum vertex cover problem
- On total functions, existence theorems and computational complexity
- Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
- A modified Lin--Kernighan traveling-salesman heuristic
- The complexity of searching succinctly represented graphs
- A new adaptive multi-start technique for combinatorial global optimizations
- Routing problems: A bibliography
- Computational aspects of the colorful Carathéodory theorem
- Metaheuristics: A bibliography
- Memetic algorithms: The polynomial local search complexity theory perspective
- A note on the complexity of local search problems
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)
