betaFeedback

WorksComputer Science

A Common Improved Bound for Asymmetric TSP and Path TSP

Abstract

We give polynomial-time (R∗+ε)(R_*+\varepsilon)-approximation algorithms for asymmetric TSP and asymmetric path TSP, for every fixed ε>0\varepsilon>0, where R∗=6+2+15+62≈12.2604R_*=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∗R_*. This improves the previous guarantees of below 14.714.7 for asymmetric TSP and 1515 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 1515 to below 14.714.7, matching his asymmetric TSP guarantee.

Introduction

The asymmetric traveling salesman problem (ATSP) asks for a minimum-cost tour visiting every vertex of a directed graph with nonnegative arc costs. In asymmetric path TSP, the walk must start at a given vertex ss and end at a given distinct vertex tt. We allow repeated vertices and arcs; on a complete directed metric, shortcutting gives a Hamiltonian tour or an (s,t)(s,t)-path.

The first constant-factor approximation for ATSP was obtained by Svensson, Tarnawski, and Végh [6]. Their laminar framework was subsequently improved by Traub and Vygen [8, 9] and by Vygen [11], who gives a tour factor below 14.7 and an (s,t)(s,t)-path factor of 15. We improve both guarantees to a common factor. Let LP⁡(G,c)\operatorname{LP}(G,c) and LP⁡s,t(G,c)\operatorname{LP}_{s,t}(G,c) denote the optima of the standard tour and path subtour relaxations, defined in § 3, and set

R∗=6+2+15+62≈12.2604.R_* = 6+\sqrt{2}+\sqrt{15+6\sqrt{2}}\approx12.2604.

Theorem 1.1 (Approximation guarantees). For every fixed ε>0\varepsilon>0, there are polynomial-time algorithms that, on nonnegative rational arc costs, return a spanning tour of cost at most (R∗+ε)LP⁡(G,c)(R_*+\varepsilon)\operatorname{LP}(G,c) and a spanning ss-tt walk of cost at most (R∗+ε)LP⁡s,t(G,c)(R_*+\varepsilon)\operatorname{LP}_{s,t}(G,c), respectively. The ATSP input is strongly connected; the path input has a feasible path relaxation. The integrality ratio of each relaxation is at most R∗R_*.

Our tour improvement builds on Svensson’s algorithm [7], as formulated for vertebrate pairs by Traub and Vygen [9 Algorithm 7.19]. Such a pair consists of a strongly laminar instance and a connected Eulerian backbone BB meeting every nonsingleton laminar set. Following Traub and Vygen [9 Definition 7.7], a (κ,η)(\kappa,\eta)-algorithm adds arcs HH so that B∪HB \cup H is a spanning tour and

c(H)≤κ LP+η∑v∉V(B)2yvc(H) \le\kappa\ \mathrm{LP} + \eta\sum_{v \notin V(B)} 2y_v

where yvy_v is the singleton dual weight at vv. Thus κ\kappa charges the LP value, and η\eta charges the singleton weight missed by the backbone. Our strengthened subtour cover gives a (2,η)(2,\eta)-algorithm for every η>3+22\eta> 3 + 2\sqrt{2}, improving Vygen’s η>4+22\eta> 4 + 2\sqrt{2} guarantee [11 Theorem 3]. We further improve the recursive reduction to vertebrate pairs by retaining the paths chosen through contracted regions. The dual weight visited by these paths reduces the cost of completing those regions, yielding the tour bound in Theorem 1.1.

Our second result strengthens the reduction from asymmetric path TSP to vertebrate pairs. It applies to any algorithm with the standard guarantee above, independently of our subtour-cover construction.

Theorem 1.2 (Transfer from vertebrate pairs). Let κ≥1\kappa\ge1 and η≥0\eta\ge0 be fixed rational constants. A polynomial-time (κ,η)(\kappa,\eta)-algorithm for vertebrate pairs gives polynomial-time LP-relative approximation algorithms with factors

ATSP:3κ+η+2,asymmetric path TSP:max⁡{3κ+η+2, 4κ+5−4κ+42κ+η+2}.\begin{aligned} \textit{ATSP:}\quad&3\kappa+ \eta+ 2,\\ \textit{asymmetric path TSP:}\quad&\max\left\{3\kappa+ \eta+ 2,\ 4\kappa+ 5 - \frac{4\kappa+ 4}{2\kappa+ \eta+ 2}\right\}. \end{aligned}

The tour factor is the established reduction to vertebrate pairs [9 Theorem 7.12]; our contribution is the smaller path factor. The proof also accommodates the refined recursive reduction of Traub and Vygen [9 Exercises 7.5–7.7], giving a path guarantee that matches Vygen’s refined tour bound (Corollary 7.4). Finally, the same path construction uses our stronger recursive estimate to obtain the path bound in Theorem 1.1. This last application uses the retained-path analysis in addition to the (2,η)(2,\eta)-guarantee.

Relation to previous work. Table 1 summarizes the recent approximation guarantees. Earlier tour-to-path reductions relate the two problems in several ways. Feige and Singh [2 Theorem 2] give a general directed reduction with a multiplicative loss of 2+ε2+\varepsilon. At the level of the subtour LP, Köhne, Traub, and Vygen [4] prove that a tour integrality ratio of ρ\rho implies a path integrality ratio of at most 4ρ−34\rho-3. For the symmetric problem, Traub, Vygen, and Zenklusen [10] preserve the approximation ratio up to an arbitrarily small additive error.

WorkATSPAsymmetric path TSP
Thin-tree rounding [1]O(log⁡n/log⁡log⁡n)O(\log n/\log\log n)—
Svensson, Tarnawski, and Végh [6]; Köhne, Traub, and Vygen [4]5062021
Traub and Vygen [8]22+ε22+\varepsilon—
Traub and Vygen [9]17+ε17+\varepsilon17+ε17+\varepsilon
Vygen [11]<14.7<14.715
This paperR∗+εR_*+\varepsilonR∗+εR_*+\varepsilon

Table 1. Selected LP-relative approximation guarantees, for fixed ε>0\varepsilon> 0. The first algorithm is randomized; the others are deterministic. The first path entry uses the reduction of Köhne, Traub, and Vygen, as stated in [6 Corollary 11.4]. A dash indicates that no path bound is listed.

More closely related to our work, Traub and Vygen [9 Theorem 9.23 and Corollary 9.24] already obtained a common 17+ε17+\varepsilon guarantee for asymmetric tours and paths. Their reduction uses the guarantee for augmenting a partial solution, rather than only a complete-tour approximation factor. Its application to Vygen’s algorithm gives a path factor of 15, so it does not carry his improved tour factor over to paths.

Thin-tree rounding provides another approach to ATSP [1]. OpenAI’s recent preprint [5] gives a deterministic polynomial-time construction of strong thin trees with an unspecified universal constant. This provides another route to constant-factor approximation. Our explicit bounds refine the recursive laminar framework.

Organization. Section 2 gives the technical overview; Section 3 fixes notation. Sections 4–6 prove the boundary-closure, subtour-cover, and recursive-augmentation results. Section 7 proves the transfer and approximation guarantees. Appendix A treats concentrated boundary ports.

Technical overview

The tour improvement comes from accounting for a route through a contracted region together with the cost of completing that region. We first recall why the existing algorithms use this recursive representation. We then explain how retaining the actual routes improves the recursive analysis, how the stronger subtour cover pays for the connections, and how the resulting augmentation guarantee transfers to (s,t)(s,t)-paths.

The recursive framework

The subtour LP supplies a fractional solution and a lower bound against which to charge the algorithm. To make this lower bound useful locally, Svensson, Tarnawski, and Végh [6] reduce ATSP to instances whose arc costs are represented by weighted cuts. The sets defining these cuts form a laminar family: any two are nested or disjoint. The reduction preserves the LP-relative approximation factor [9 Theorem 7.4]. We refer to it as the laminar reduction. After this reduction, an arc costs the sum of the weights of the cuts it crosses. These cuts are tight for the supplied fractional solution, so each contributes twice its weight to the LP value. We call this contribution its dual mass. The nested sets can now serve as regions for a recursive algorithm, with an explicit share of the lower bound assigned to each region.

The recursion starts with a connected Eulerian multigraph, called a partial backbone, and extends it until it spans the graph. Within a region WW, it contracts the inclusion-maximal proper positive-weight laminar sets missed by the partial backbone. The contracted graph is a simpler instance in which these missed regions are represented by vertices. A solution on this quotient is lifted by replacing every visit to a contracted vertex by a path between its original entry and exit. The contracted regions are then completed recursively. This architecture is inherited from Svensson, Tarnawski, and Végh [6 Section 9.2] and Traub and Vygen [9 Algorithm 7.8 and Lemma 7.13].

The quotient is where Svensson’s algorithm is used: the image of the backbone meets every remaining nonsingleton laminar set, giving a vertebrate pair. On such an instance, the algorithm maintains a local Eulerian solution outside the backbone. Here local means that an arc crosses no nonsingleton laminar cut. If yvy_v denotes the weight of the singleton cut at vv, a local arc uvuv has cost yu+yvy_u+y_v. A simple local circuit CC therefore costs ∑v∈V(C)2yv\sum_{v\in V(C)} 2y_v; for a general local Eulerian multiset, the same accounting counts each visit. This identity lets the algorithm allocate vertex budgets and charge circuits to the components they meet. A subtour cover supplies connections between the current components and to the backbone. Its components meeting the backbone may use nonlocal arcs. Vygen [11 Sections 2–4] improves the initialization and charging analysis within this framework.

Retaining passage costs and recursive progress

In a recursive call, a quotient vertex represents an entire laminar region. Its entry and exit determine which internal path must be restored when the solution is lifted. For each endpoint pair, the reduction fixes one of the nice paths of Traub and Vygen [9 Lemma 7.5]: it lies in the smallest laminar set containing its endpoints (allowing the whole graph) and crosses each laminar boundary at most once in each direction. The basic recursive reduction assigns a fixed charge to the quotient vertex large enough to pay for every such path. Our extension of Svensson’s algorithm retains the actual entry, exit, and path of each selected passage instead.

This information links the cost of lifting to progress within the region. The nice-path identity [9 Lemma 7.6] equates the path cost, together with its entry and exit contributions, to the dual mass of the laminar sets it visits. We call this visited mass its coverage. A passage of small coverage is cheap but leaves more mass for recursive completion; a passage of large coverage is more expensive but can reduce the completion cost. Our extension of the initialization and charging analysis bounds the total cost of the retained passages while keeping this coverage available to the recursive analysis.

Coverage must belong to a connected object from which recursion can continue. Quotient connectivity alone does not provide such an object: two circuits meeting at one contracted vertex may lift to disjoint closed walks. For each contracted region LL, we select a retained passage of maximum coverage. When processing LL, the whole current connected Eulerian component containing that passage is a possible backbone BLB_L; it may extend outside LL. Its coverage is certified before the recursive call. Augmenting BLB_L with arcs inside LL to visit every vertex of LL then joins all other lifted components meeting LL. Figure 1 illustrates the loss of connectivity under lifting and its restoration by an internal augmentation.

Lifting can disconnect circuits; internal Eulerian augmentation restores connectivity

Figure 1. Lifting can disconnect circuits; internal Eulerian augmentation restores connectivity.

The recursive algorithm compares completing this inherited component with starting from a fresh partial backbone, as in the refined reduction of Traub and Vygen [9 Exercises 7.5–7.6]. Retaining passage-dependent costs improves the accounting of this choice. The resulting augmentation bound decreases with the dual mass already visited by the inherited backbone (Theorem 6.4). Svensson’s algorithm and the recursive completion have distinct roles: the former joins components in the quotient, whereas the latter completes contracted regions in the original graph.

Paying for subtour-cover repairs

To apply the subtour-cover algorithm inside a recursive region, we first need a fractional comparison circulation there. Restricting the original flow to the region can destroy balance. We choose and price internal return paths to restore it, while retaining the attachment information needed when the quotient solution is lifted (§ 4). This construction also accounts for the fresh backbone choices used by the recursion.

The subtour cover used by Vygen rounds a modified fractional circulation and then repairs the entry–exit pairing chosen by rounding. Its cost bound pays for these repairs through an additional singleton-mass term [9 Theorem 8.24]. We include the repair prices in the rounding objective and obtain

c(F)≤2cTx,c(F) \le2c^{\mathsf{T}}x,

where FF is the cover and xx is the supplied fractional comparison circulation. The difficulty is that rounding may choose a different pairing from the fractional one. We price all possible repair pairings and pay for them with fractional paths and cycles removed before rounding. This preserves the locality, degree bounds, and backbone visits required by Svensson’s algorithm and by recursive lifting (Theorem 5.1). The stronger cover reduces the cost of connecting quotient components; passage-dependent accounting reduces the cost of completing their contracted regions. The tour analysis combines these two improvements.

From augmentation to (s,t)(s,t)-paths

The augmentation guarantee keeps information that a complete-tour factor does not express: the cost of completion decreases with the mass already covered by the partial solution. Our transfer uses this information to compare two initial walks before augmentation.

The standard normalization of the path LP supplies two inexpensive (s,t)(s,t)-paths in the support of its fractional solution [9 Lemmas 9.9, 9.10, and 9.16]. One initial walk preserves both path sections within every strongly connected component. The other visits a maximum-coverage path from the fixed nice-path family in each component and connects it to the entry and exit. The component maximum coverages bound the added connector costs in the first construction; in the second, they also certify mass that no longer needs completion. The first completion bound increases with their sum, whereas the second decreases with it. Keeping this shared quantity in both bounds and selecting the better construction avoids the loss incurred by bounding each one separately.

The algorithm completes only the selected walk, with one augmentation call per component. To apply Eulerian augmentation, it closes the walk by one auxiliary return from tt to ss. The component augmentations use only internal arcs, so removing this return from the resulting Euler tour gives a spanning (s,t)(s,t)-walk. § 7.2 gives the two constructions and proves the strengthened reduction to vertebrate pairs, then applies the same analysis to our recursive augmentation.

Preliminaries

Parallel arcs and multiset unions are allowed, and all costs count multiplicity. We discard self-loops. We call an arc multiset Eulerian when indegree equals outdegree at every vertex; connectivity is stated separately. “Connected” refers to the underlying undirected graph. A balanced connected multigraph is strongly connected on its vertices and has an Euler tour. A single vertex with no arcs is an allowed connected Eulerian multigraph.

For a vertex set SS, let δ+(S)\delta^{+}(S) and δ−(S)\delta^{-}(S) be its outgoing and incoming arcs, and put δ(S)=δ+(S)∪δ−(S)\delta(S)=\delta^{+}(S)\cup\delta^{-}(S). Write div⁡x(v)=x(δ+(v))−x(δ−(v))\operatorname{div}x(v)=x(\delta^{+}(v))-x(\delta^{-}(v)). The tour relaxation is

LP⁡(G,c)=min⁡{cTx:div⁡x=0, x(δ−(S))≥1 (∅≠S⊊V), x≥0}.(1)\operatorname{LP}(G,c)=\min\{c^{T}x:\operatorname{div}x=0,\ x(\delta^{-}(S))\ge1\ (\varnothing\ne S\subsetneq V),\ x\ge0\}. \tag*{(1)}

For asymmetric path TSP with terminals s,ts,t, replace balance by div⁡x=1s−1t\operatorname{div}x=\mathbf{1}_{s}-\mathbf{1}_{t} and impose x(δ+(S))≥1x(\delta^{+}(S))\ge1 for every nonempty S⊆V∖{t}S\subseteq V\setminus\{t\}. Denote its optimum by LP⁡s,t(G,c)\operatorname{LP}_{s,t}(G,c).

Strongly laminar instances and path coverage

A strongly laminar instance consists of a strongly connected digraph GG, a laminar family L\mathcal{L} of nonempty proper vertex sets, a circulation x>0x>0 feasible for (1), and weights yL>0y_L>0. Every G[L]G[L] is strongly connected and x(δ−(L))=1x(\delta^{-}(L))=1. The induced arc cost is cy(e)=∑L:e∈δ(L)yLc_y(e)=\sum_{L:e\in\delta(L)}y_L, so cyTx=∑L2yL=LP⁡(G,cy)c_y^{T}x=\sum_L2y_L=\operatorname{LP}(G,c_y).

For singleton weights, write yv=y{v}y_v=y_{\{v\}} when {v}∈L\{v\}\in\mathcal{L} and yv=0y_v=0 otherwise. A vertebrate pair consists of a strongly laminar instance and a connected Eulerian backbone BB meeting every nonsingleton laminar set. Following Traub and Vygen [9 Definition 7.7] and Vygen [11], a (κ,η)(\kappa,\eta)-algorithm adds an Eulerian multiset HH such that B∪HB\cup H is a spanning tour and

c(H)≤κLP⁡+η∑v∉V(B)2yv.(2)c(H)\le\kappa\operatorname{LP}+\eta\sum_{v\notin V(B)}2y_v. \tag*{(2)}

Thus κ\kappa prices the LP value and η\eta prices uncovered singleton mass. For W∈L∪{V}W\in\mathcal{L}\cup\{V\}, a partial backbone is a connected Eulerian multigraph BB with V(B)∩W≠∅V(B)\cap W\ne\varnothing, without the requirement to meet all nonsingleton sets or to be contained in $W. This is the more general input in [9 Lemma 7.13]. When a recursive construction chooses a new partial backbone, we call it fresh to distinguish it from the inherited one.

Proposition 3.1 (Laminar reduction and nice paths). The following operations are polynomial time [9 Theorem 7.4 and Lemmas 7.5–7.6].

(i) A ratio-ρ\rho algorithm for strongly laminar instances gives the same LP-relative ratio for arbitrary nonnegative-cost ATSP. The reduction restricts to an optimal primal support and supplies potentials with cy(uw)=c(uw)+πu−πvc_y(uw)=c(uw)+\pi_u-\pi_v. Eulerian outputs on this support have the same original and induced costs.

(ii) For W∈L∪{V}W\in\mathcal{L}\cup\{V\} and u,v∈Wu,v\in W, one can find a simple path PuvWP^W_{uv} lying in their smallest laminar container and entering and leaving every laminar set at most once.

Following the terminology of [9 Lemma 7.5], call these paths nice. Fix these paths once and for all, allowing PuvWP^W_{uv} to consist only of uu. Our augmentation theorem applies to any such fixed family. For the classical bounds in § 7.2, we use the global choice of [9 Section 7.3]: the same path for each endpoint pair is used in every containing region, independently of the dual weights. In both settings the caller and all recursive calls retain the chosen paths. All subsequent arcs stay on the support, and we write c=cyc=c_y until the path normalization in § 7.2. For a region WW, its descendant mass and vertex endpoint weights are

MW=∑J∈L:J⊊W2yJ,hW(u)=∑J∈L:J⊆W, u∈JyJ.(3)M_W=\sum_{J\in\mathcal{L}:J\subsetneq W}2y_J,\qquad h_W(u)=\sum_{J\in\mathcal{L}:J\subseteq W,\ u\in J}y_J. \tag*{(3)}

For a vertex set SS, define

cov⁡W(S)=∑J∈L,J⊊WJ∩S≠∅2yJ.\operatorname{cov}_{W}(S)=\sum_{\substack{J\in\mathcal{L},\,J\subsetneq W\\J\cap S\ne\varnothing}}2y_J.

For a path or subgraph HH, write cov⁡W(H)=cov⁡W(V(H))\operatorname{cov}_{W}(H)=\operatorname{cov}_{W}(V(H)). The maximum coverage of a fixed nice path is

dW=max⁡u,v∈Wcov⁡W(PuvW).d_W=\max_{u,v\in W}\operatorname{cov}_{W}(P_{uv}^{W}).

This maximum is over a polynomial-size path family. In the notation of Traub and Vygen [9 Section 7.3], MWM_W is value⁡(W)\operatorname{value}(W), cov⁡W(PuvW)\operatorname{cov}_{W}(P_{uv}^{W}) is DW(u,v)D_W(u,v), and dWd_W is DWD_W. For a partial backbone BB, cov⁡W(B)\operatorname{cov}_{W}(B) is their DW(B)D_W(B) from [9 Exercise 7.5].

References

  1. [1][AGM+10] Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 379–389. SIAM, 2010. doi:10.1137/1.9781611973075.32.DOI
  2. [2][FS07] Uriel Feige and Mohit Singh. Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 4627 of Lecture Notes in Computer Science, pages 104–118. Springer, 2007. URL: https://www2.isye.gatech.edu/~msingh94/publications/atsp.pdf.DOI
  3. [3]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. doi:10.1007/978-3-642-97881-4.DOI
  4. [4]Anna Köhne, Vera Traub, and Jens Vygen. The asymmetric traveling salesman path LP has constant integrality ratio. Mathematical Programming, 183(1–2):379–395, 2020. doi:10.1007/s10107-019-01450-8.
  5. [5]OpenAI. A polynomial-time construction of strong thin trees. OpenAI Math Release preprint, 2026. URL: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-polynomial-time-construction-of-strong-thin-trees-September-23-2026/paper.pdf.
  6. [6]Ola Svensson, Jakub Tarnawski, and László A. Végh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM, 67(6):37:1–37:53, 2020. doi:10.1145/3424306.DOI
  7. [7]Ola Svensson. Approximating ATSP by relaxing connectivity. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1–19. IEEE, 2015. doi:10.1109/FOCS.2015.10.DOI
  8. [8]Vera Traub and Jens Vygen. An improved approximation algorithm for the asymmetric traveling salesman problem. SIAM Journal on Computing, 51(1):139–173, 2022. doi:10.1137/20M1339313.DOI
  9. [9]Vera Traub and Jens Vygen. Approximation Algorithms for Traveling Salesman Problems. Cambridge University Press, 2025. doi:10.1017/9781009445436.DOI
  10. [10]Vera Traub, Jens Vygen, and Rico Zenklusen. Reducing path TSP to TSP. SIAM Journal on Computing, 51(3):STOC20–24–STOC20–53, 2022. doi:10.1137/20M135594X.
  11. [11]Jens Vygen. Better approximation guarantee for Asymmetric TSP, 2026. arXiv:2603.14334v1.arxiv.org/abs/2603.14334

Paper details

vlnc:W_43667dwf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents