Improved approximation algorithms lower bounds for asymmetric TSP problems

A Common Improved Bound for Asymmetric TSP and Path TSP

Data Structures and Algorithms

Summary

Finding the shortest possible route that visits a list of places once and returns to the start is very hard, especially when travel costs differ by direction. The authors improved algorithms that quickly find routes for these tricky cases, asymmetric traveling salesman problems and path TSPs, with better quality guarantees than before. Their new methods build on existing techniques and offer tighter bounds on how close the solutions are to the best possible routes. This means more efficient routing in situations where directions and costs matter differently, such as logistics or vehicle routing.

What this means in practice

  • For logistics planners: Develop routing solutions for delivery networks where travel costs vary by direction using improved approximation algorithms with tighter quality guarantees.
  • For vehicle routing software teams: Incorporate enhanced path-finding methods for asymmetric distance data to generate more efficient routes in transportation management systems.

Authors

MohammadTaghi Hajiaghayi, Changki Yun

Abstract

We give polynomial-time $(R_*+\varepsilon)$-approximation algorithms for asymmetric TSP and asymmetric path TSP, for every fixed $\varepsilon>0$, where $R_*=6+\sqrt2+\sqrt{15+6\sqrt2}\approx12.2604$. Both guarantees hold relative to the corresponding subtour relaxations, whose integrality ratios are therefore at most $R_*$. This improves the previous guarantees of below $14.7$ for asymmetric TSP and $15$ for asymmetric path TSP [Vygen, 2026]. Our algorithms strengthen subtour covers and recursive augmentation in the laminar framework [Svensson, Tarnawski, Vegh, JACM'20; Traub, Vygen, 2025]. The recursive analysis retains the paths through contracted regions and accounts jointly for their cost and the dual mass they visit. We also improve the reduction from asymmetric path TSP to vertebrate pairs [Traub, Vygen, 2025] by comparing two initial walks with complementary completion bounds. Applied to Vygen's existing vertebrate-pair algorithm, this reduction alone improves the path factor from $15$ to below $14.7$, matching his asymmetric TSP guarantee.