YoVDO

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

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Travelling Salesman Problem (TSP) Courses Mathematical Analysis Courses Theoretical Computer Science Courses Optimization Algorithms Courses Traveling Salesman Problem Courses

Course Description

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

Related Courses

Delivery Problem
University of California, San Diego via Coursera
Dynamic Programming
YouTube
What Is the Best Way to Lace Your Shoes? Dream Proof
Mathologer via YouTube
The Traveling Salesman Problem - When Good Enough Beats Perfect
Reducible via YouTube
Asymmetric Traveling Salesman Problem: Advances and Challenges - Session 1A
Association for Computing Machinery (ACM) via YouTube