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

DOI10.1137/0221030zbMath0761.68048OpenAlexW2047820376MaRDI QIDQ4016908

Christos H. 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)

Related Items

A new adaptive multi-start technique for combinatorial global optimizations, Routing problems: A bibliography, Metaheuristics: A bibliography, Finding optimal subgraphs by local search, The complexity of searching implicit graphs, Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, A note on the complexity of local search problems, The complexity of searching succinctly represented graphs, Computational aspects of the colorful Carathéodory theorem, Memetic algorithms: The polynomial local search complexity theory perspective, A survey of very large-scale neighborhood search techniques, On the distributed decision-making complexity of the minimum vertex cover problem, On total functions, existence theorems and computational complexity