Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

Hausdorff Center for Mathematics via YouTube

Overview

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.

Syllabus

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

Taught by

Hausdorff Center for Mathematics

Reviews

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.