Asymmetric Traveling Salesman Problem: Advances and Challenges - Session 1A

Explore cutting-edge research on the Traveling Salesman Problem (TSP) in this 40-minute conference talk from STOC 2020. Delve into the Asymmetric Traveling Salesman Problem, examining theorems, algorithms, and state-of-the-art approaches. Investigate lower bounds, past TSP reductions, and approximation results. Consider the challenges of Path TSP and its potential increased difficulty. Gain insights into key technical contributions and engage with thought-provoking questions. Conclude with an exploration of Half Integral TSP, broadening your understanding of this fundamental problem in computer science and optimization.

Introduction
Asymmetric Traveling Salesman Problem
Background
Theorem
Algorithm
State of Yard
Lower Bounds
Reducing Past TSP
Approximation Results
Is Path TSP Harder
Path TSP Gap
Key Technical Contribution
Questions
Half Integral TSP