Approximating Asymmetric Traveling Salesman Problems via Integrality Gaps

125 concepts42 papers1 proposal

The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization. While the symmetric version—where the distance from city A to B equals the distance from B to A—has long been approachable via the 1.5-approximation of Christofides’ algorithm, the Asymmetric TSP (ATSP) remained a significant challenge for decades. The central difficulty lies in the integrality gap of the standard linear programming (LP) relaxation, known as the Held-Karp relaxation. This gap measures the worst-case ratio between the optimal integer solution (the shortest tour) and the optimal fractional solution provided by the LP.

The Held-Karp Relaxation and the Constant Factor Breakthrough

To solve the ATSP, researchers often start by relaxing the requirement that edges must be chosen in whole units (0 or 1). Instead, the LP allows for "fractional" edges, provided that the total flow into and out of every city is equal and that every subset of cities is connected. The value of this relaxation provides a lower bound on the true optimal tour.

For a long time, the best known approximation algorithms for ATSP had ratios that grew with the number of nodes (logarithmic bounds). However, Svensson et al. achieved a major breakthrough by providing the first constant-factor approximation algorithm for ATSP. The authors achieved this by reducing the general ATSP to a more structured "Subtour Partition Cover" problem. This result confirmed the long-standing conjecture that the integrality gap of the Held-Karp relaxation is a constant, rather than a function of the graph size.

Earlier work by Svensson had already demonstrated that for specific cases, such as node-weighted shortest path metrics, the integrality gap is bounded by a constant factor of 15 [Svensson]. Further progress by Tarnawski et al. extended these techniques to graphs with two distinct edge weights, providing a 901-approximation and marking a critical step toward the general constant-factor solution.

Closing the Gap: The 4/3 Conjecture

In the realm of Graphic TSP—where distances correspond to shortest paths in an unweighted graph—the focus shifts from finding any constant factor to reaching the "holy grail" ratio of 4/3. This value is conjectured to be the true integrality gap for the subtour elimination LP in symmetric cases.

Recent research has chipped away at this barrier by focusing on "hard" instances. Jin et al. developed a randomized 4/3-approximation for "half-integral cycle cut instances," which are often the most difficult worst-case examples for the LP. By using a top-down induction approach and Markov chain analysis, the authors proved that the 4/3 bound is achievable for these specific structures.

Similarly, for specialized graph classes, the 4/3 barrier has already been breached:

  • Cubic Graphs: Aggarwal et al. presented a polynomial-time algorithm that achieves a 4/3 approximation for cubic 3-edge-connected graphs by constructing a connected Eulerian subgraph with at most $4n/3$ edges.
  • Cubic Bipartite Graphs: Karp et al. pushed this even further, achieving a 9/7 approximation ratio. Their analysis highlighted that managing 6-cycles is the primary obstacle to improving these bounds.
  • 2-Connected Cubic Graphs: Correa et al. proved that the upper bound for these graphs is strictly lower than 4/3, suggesting the integrality gap is even smaller for this class.

Structural Insights and Spanners

Beyond specific ratios, the research direction emphasizes how graph topology influences tour construction. For example, the existence of "light spanners"—subgraphs that preserve distances without adding much total weight—is a powerful tool. Le and Borradaile proved that H-minor-free graphs possess these light spanners, which Le later used to develop the first Polynomial Time Approximation Scheme (PTAS) for the subset TSP in minor-free graphs [Le].

These structural properties also allow for efficiency gains. Behnezhad et al. introduced sublinear-time algorithms that estimate the cost of a TSP tour without examining the entire graph, achieving a $(1/2 - \epsilon)$-approximation for maximum path covers to break efficiency barriers for Graphic TSP.

The Search for Worst-Case Instances

While theorists work to lower the upper bounds of the integrality gap, others work from the bottom up to find the most difficult instances. Vercesi et al. utilized the geometric symmetries of the LP relaxation polytope to discover new ATSP instances with high integrality gaps. By pushing the known lower bounds for problems up to 22 nodes, the authors provide a "stress test" for current solvers and approximation theories, helping to determine if the true gap for ATSP might eventually be proven as low as 2.

Through these combined efforts—bounding the gap for general ATSP, targeting the 4/3 ratio in Graphic TSP, and exploiting specific graph structures—the field is moving toward a complete understanding of the limits of linear programming for routing problems.

Key Foundational Work

A New Bound for the 2-Edge Connected Subgraph Problem (1998) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_asymmetric_traveling_salesman_problem_ap_e209048d,
  title = {asymmetric traveling salesman problem approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-traveling-salesman-problem-approximation/rdr_e209048d6c9248c4864c1433bdc13f94},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_asymmetric_traveling_salesman_problem_ap_e209048d_v1,
  title = {asymmetric traveling salesman problem approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-traveling-salesman-problem-approximation/rdr_e209048d6c9248c4864c1433bdc13f94/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake