The Approximation Ratio of the k-Opt Heuristic for Euclidean TSP
Offered By: Hausdorff Center for Mathematics via YouTube
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
Intro to AlgorithmsUdacity Games without Chance: Combinatorial Game Theory
Georgia Institute of Technology via Coursera Calculus Two: Sequences and Series
Ohio State University via Coursera Big Data: from Data to Decisions
Queensland University of Technology via FutureLearn Simulation and Modeling for Engineering and Science
Georgia Institute of Technology via edX