The Approximation Ratio of the k-Opt Heuristic for Euclidean TSP

Explore the k-Opt heuristic for the Traveling Salesman Problem in this 32-minute lecture by Stefan Hougardy from the Hausdorff Center for Mathematics. Delve into the improved approximation ratio for 2-dimensional Euclidean TSP instances, learning how it achieves Θ(log n/ log log n) for n cities. Discover the enhancement over the previous O(log n) upper bound and the introduction of a non-trivial lower bound for k ≥ 3. Gain insights into the heuristic's application across various p-norms and understand the collaborative research behind these findings.