Explore the reduction of Path TSP to TSP in this 25-minute ACM conference talk. Delve into the background of the canonical idea, examine large distance scenarios, and analyze special cases through examples. Gain insights into this important topic in computational complexity theory and optimization algorithms, concluding with a comprehensive understanding of the reduction process and its implications.
Overview
Syllabus
Introduction
Background
canonical idea
large distance
special cases
example
conclusion
Taught by
Association for Computing Machinery (ACM)
Related Courses
-
A 1.5-Approximation for Path TSP
-
Matthias Mnich - Time- and Space-Optimal Algorithms for the Many-Visits TSP
-
NP-Complete Problems
-
Data Structures and Performance
4.0 -
Asymmetric Traveling Salesman Problem: Advances and Challenges - Session 1A
-
The Traveling Salesman Problem - When Good Enough Beats Perfect
