An Improved Approximation Algorithm for ATSP
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
Explore an improved approximation algorithm for the Asymmetric Traveling Salesman Problem (ATSP) in this 24-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into the history of approximation ratios for ATSP and learn about linear programming relaxation. Discover a sequence of reductions and strongly laminar instances, followed by an examination of a naive recursive algorithm. Analyze nice paths and understand recursion with vertebrate pairs. Gain insights into constructing the backbone and conclude with a summary of the current state of the art for ATSP.
Syllabus
Intro
The asymmetric traveling salesman problem
History of approximation ratios for ATSP
Linear Programming Relaxation
Overview: sequence of reductions
Strongly laminar instances
Naive recursive algorithm
Analysis: nice paths
Recursion with vertebrate pairs
Constructing the backbone
Summary: State of the Art for ATSP
Taught by
Association for Computing Machinery (ACM)
Related Courses
Approximation Algorithms Part IÉcole normale supérieure via Coursera Approximation Algorithms Part II
École normale supérieure via Coursera Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford University via Coursera Algorithm Design and Analysis
University of Pennsylvania via edX Delivery Problem
University of California, San Diego via Coursera