The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k \(\geq\) 5

Sophia Heimann, Phuc Hung Hoang, Stefan Hougardy
January 2024
PDF bib Project DOI

Abstract

Full Citation:

Sophia Heimann, Hung P. Hoang, Stefan Hougardy. The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k (\geq) 5. 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann and Martin Grohe and Gabriele Puppis and Ola Svensson), volume 297 of LIPIcs, pages 84:1-84:18, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

Type
Conference Paper
ParAI
Phuc Hung Hoang
Phuc Hung Hoang

Phuc Hung Hoang is a Project Assistant at the Algorithms and Complexity Group.