TOPICS
Search

Asymmetric Traveling Salesman Problem


The asymmetric traveling salesman problem asks for a minimum-cost closed walk visiting every graph vertex of a directed graph with nonnegative arc costs. The costs of travel in opposite directions may differ. On a complete directed metric, where costs satisfy the directed triangle inequality, repeated vertices can be shortcut to obtain a Hamiltonian cycle without increasing cost (Svensson et al. 2020). The path version instead prescribes distinct start and end vertices s and t and asks for a minimum-cost spanning s-t walk (Köhne et al. 2020).

A subtour linear programming relaxation assigns nonnegative fractional multiplicities x_e to the arcs. For tours, incoming and outgoing multiplicities balance at each graph vertex, and every nonempty proper vertex subset has total incoming multiplicity at least 1. For paths, outgoing minus incoming multiplicity is 1 at s, -1 at t, and zero elsewhere; every nonempty vertex subset excluding t must have outgoing multiplicity at least 1. In both cases the objective minimizes the sum of arc costs times multiplicities.

Hajiaghayi and Yun (2026, Theorem 1.1) gave deterministic algorithms with common approximation factor R_*+epsilon for every fixed epsilon>0, where

 R_*=6+sqrt(2)+sqrt(15+6sqrt(2))=12.2604....

For nonnegative rational costs, the algorithms run in polynomial time, with the polynomial allowed to depend on epsilon. The tour input is strongly connected; for the path version, the stated path relaxation must be feasible. The returned cost is at most R_*+epsilon times the optimum of the corresponding subtour relaxation, and therefore also at most this factor times the true optimum. Consequently, each relaxation has integrality gap at most R_*. The statement is an approximation guarantee, rather than an exact algorithm for either problem.


See also

Directed Graph, Hamiltonian Cycle, Integrality Gap, Linear Programming, Traveling Salesman Problem

Explore with Wolfram|Alpha

References

Hajiaghayi, M. and Yun, C. "A Common Improved Bound for Asymmetric TSP and Path TSP." 13 Nov 2026. https://arxiv.org/abs/2611.18498v1.Köhne, A.; Traub, V.; and Vygen, J. "The Asymmetric Traveling Salesman Path LP Has Constant Integrality Ratio." Math. Programming 183, 379-395, 2020. https://doi.org/10.1007/s10107-019-01450-8.Svensson, O.; Tarnawski, J.; and Végh, L. A. "A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem." J. ACM 67, 37, 2020. https://doi.org/10.1145/3424306.

Cite this as:

Weisstein, Eric W. "Asymmetric Traveling Salesman Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AsymmetricTravelingSalesmanProblem.html

Subject classifications