A Near-Complete Resolution of the Exponential-Time Complexity of k-opt for the Traveling Salesman Problem.

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

Browse the full SODA paper archive.