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 and
and asks for a minimum-cost spanning
-
walk (Köhne et al. 2020).
A subtour linear programming relaxation assigns nonnegative fractional multiplicities 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
,
at
, and zero elsewhere; every nonempty vertex subset excluding
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 for every fixed
, where
For nonnegative rational costs, the algorithms run in polynomial time, with the polynomial allowed to depend on . The tour input is strongly
connected; for the path version, the stated path relaxation must be feasible.
The returned cost is at most
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
. The statement is an approximation guarantee, rather
than an exact algorithm for either problem.