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

YouTube

An Improved Approximation Algorithm for ATSP

Association for Computing Machinery (ACM) via YouTube

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)

Reviews

Start your review of An Improved Approximation Algorithm for ATSP

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.