TSP with Predictions: Heatmap to Tour with Provable Guarantees

Adam Polak; Eleonora Vercesi; Fabrizio Grandoni; Marek Eli\'a\v{s}

REVIEW 2 major objections 5 minor 35 references

TSP with Predictions: Heatmap to Tour with Provable Guarantees

T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A TSP heatmap can be decoded into a tour with cost at most optimum plus 2η, where η is the heatmap's weighted L1 error against some optimal tour.

desk verdict Theorem 1.1's heatmap-to-tour guarantee is the real new result and looks correct; the graphical-TSP Theorem 1.3 has a proof gap as written—the algebra misses by w(H−). read the letter →

arxiv 2607.03791 v2 pith:SRTOL65W submitted 2026-07-04 cs.DS cs.LG

Marek Eliáš , Fabrizio Grandoni , Adam Polak , Eleonora Vercesi This is my paper · ORCID

classification cs.DScs.LG

keywords TSPalgorithmswithpredictionslearning-augmentedheatmapminimumspanningtreeandmatchingheuristicmetricgraphicalapproximationguarantee

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that a machine-learned heatmap — a number between 0 and 1 for each edge indicating whether it belongs to an optimal TSP tour — can be converted into a real tour with a certified guarantee: if the heatmap has weighted $L_1$ error $\eta$ with respect to some optimal tour $X^*$, the algorithm returns a tour of expected weight at most $w(X^*) + 2\eta$. The result matters because the standard neural-TSP pipeline lacks such guarantees; greedy and beam-search decoders can ignore good heatmaps, while the proposed decoder provably exploits them. The paper proves the same structure in three settings: an $O(n^3)$ algorithm with $2\eta$, a near-linear $O(n^2 \log n)$ algorithm with $11\eta$, and a graphical-TSP version with near-linear time and $4\eta$ given edge-multiplicity predictions. It also proves that linear dependence on $\eta$ is unavoidable (a factor below $1 + \frac{\eta}{122 \cdot \text{OPT}}$ would refute $P \neq NP$).

What carries the argument

The load-bearing object is the reference $S$-join $J' = X^* \Delta T$, the symmetric difference of the optimal tour and the biased spanning tree. For $S = \operatorname{odd}(T)$, $J'$ is a feasible $S$-join because $T+J'$ equals $X^*$ plus every edge of $T \setminus X^*$ doubled; its weight therefore upper-bounds the optimal matching $J$. The proof decomposes $J'$ into parts corresponding to false positives and false negatives, and the same construction powers all three algorithms. In the near-linear variant, the tree is biased toward the heaviest predicted edges by flipping the sign of their weights, and a careful case analysis on the lightest edge $e^*$ of $X^*$ bounds the matching cost in terms of $\eta$ alone whenever $|S| > 2$.

What would settle it

To refute the main theorem, find a metric TSP instance and a prediction $P$ with error $\eta$ for which Algorithm 1 outputs a tour of weight strictly greater than $w(X^*) + 2\eta$; the paper's own tightness examples show equality is attainable, so any excess above $2\eta$ would disprove Theorem 4.3. To refute the lower bound, exhibit a polynomial-time algorithm with approximation factor below $1 + \frac{\eta}{122 \cdot \text{OPT}}$ for metric TSP with predictions; that would contradict Theorem 7.1 under $P \neq NP$.

Watch

Extended reading notes

Core claim

On the paper's own terms, its central discovery is that a simple classical 1.5-approximation construction — build a minimum spanning tree, then a minimum perfect matching on odd-degree vertices, then shortcut — can be made prediction-aware without losing its safety net. The algorithm samples a set $P$ of predicted edges from the heatmap, builds a minimum spanning tree $T$ in which edges of $P$ are treated as having zero weight, then computes a minimum-weight perfect matching $J$ on the odd-degree vertices of $T$ using the original edge weights, and finally shortcuts the Eulerian multigraph $T+J$ into a Hamiltonian cycle. The proof shows that both the tree and the matching deviate from the reference tour

Load-bearing premise

The edge weights must satisfy the triangle inequality; without it, no finite approximation guarantee is possible even when the prediction error is arbitrarily small (the paper proves this in Appendix B.3).

Editorial extensions

If this is right

Perfect heatmap (η=0) yields an optimal tour in expectation; any heatmap, however bad, gives a feasible tour whose cost is never uncontrolled because the underlying structure remains a 1.5-approximation.
The guarantee is stated for any tour X* simultaneously: E[w(X)] ≤ min_{tour X*} w(X*)+2η(p,X*), so a heatmap that is close to any cheap tour is sufficient.
Near-linear running time is achievable at the price of a larger constant: O(n^2 log n) with 11η, and Euclidean instances can be solved in O((n+|P|) polylog n) using Delaunay triangulation and approximate Euclidean matching.
In graphical TSP, the same strategy gives an O(m log n) algorithm with 4η, provided the prediction includes edge multiplicities; without multiplicities, the O(n^3) algorithm still works.
No polynomial-time learning-augmented algorithm for metric TSP can have approximation factor smaller than 1 + η/(122 OPT) unless P=NP, so the linear dependence on η is inherent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The analysis implies a clean reframing of heatmap training: since extra tour length is at most the weighted L1 distance between heatmap and optimal tour, a loss function that directly minimizes that weighted L1 error is aligned with final solution quality — an editorial extension, not stated in the paper.
The 2η constant is likely not tight; the lower bound only rules out factors below 1/122·(η/OPT), leaving a gap between 2 and 1/122. An improved analysis or a different construction might reduce the 2, but the paper does not claim this.
For sparse graphical instances, demanding edge multiplicities from the predictor is a real modeling cost; one could test whether supplying only a set of likely edges plus a cheap estimate of multiplicities preserves near-linear time and what error penalty that incurs.
The empirical variant that reweights edges as w(e)(1−q(e)) (called CHR+ in the paper) is not the algorithm proven in Theorem 1.1 but behaves like a smooth interpolation between Christofides and the proven algorithm; this suggests a family of practical decoders with the same theoretical backbone.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague, here's my read. The genuinely new thing is Theorem 1.1: a polynomial algorithm that turns any edge heatmap into a TSP tour with expected weight ≤ OPT + 2η, where η is the weighted L1 error against an optimal tour. That gives a certified replacement for a heuristic step in the neural combinatorial optimization pipeline. I checked the proof—Lemmas 4.4 and 4.5, the Christofides decomposition, the shortcutting under triangle inequality—and it holds. The sign-flipped MST in Algorithm 2 with Lemma 4.6 is clever, and the near-linear 11η variant checks out as far as I can tell. The linear-in-η lower bound from 123/122-inapproximability is also valid and a useful sanity check. So the metric-TSP core of the paper is a solid first contribution.

The soft spot is Theorem 1.3. The printed chain in Section 6.1 does not yield w(X*)+4η. Following their own observations: w(T)+w(J) ≤ w(T∩X*)+η + 2(η+w(H−)) + w(X*−T)+w(H+) = w(X*)+3η+2w(H−)+w(H+) = w(X*)+5w(H−)+4w(H+). That is not ≤ w(X*)+4η unless w(H−)=0. This is not a loose constant; it is an internal algebraic gap in one of the three headline theorems. It might be repairable—I don't see an obstruction—but it is not repaired in this version.

The empirical section needs recalibration too. The main tested decoder CHR+ is a continuous weighting variant, not the analyzed Algorithm 1 (disclosed in Appendix C.3). Yet Section 8 says CHR+ 'consistently outperforms' the Christofides baseline, and Table 1 contradicts that for several predictor/size combinations, e.g., DIFUSCO at n=500 and 1000 and GNN4CO at most sizes. And MCTS, which the introduction motivates against, is never benchmarked, so the narrative about the pipeline overstates what the experiments show.

Overall, if you focus on Theorem 1.1 and the lower bound, this is a worthwhile paper and should be sent to referees. Before acceptance someone needs to fix Theorem 1.3 or state a weaker guarantee, and the claims in Section 8 need to match the table. I would bring it to a reading group mainly to see whether the graphical proof can be salvaged.

Referee Report

2 major / 5 minor

Summary. The paper studies the heatmap-to-tour step for TSP in the algorithms-with-predictions framework. For a complete graph with metric weights, a heatmap p is assigned an L1 prediction error η against an optimal tour, and the paper gives algorithms whose tour length is bounded by OPT + cη: an O(n^3) Christofides-style algorithm (Algorithm 1) with constant 2 (Theorem 1.1), an O(n^2 log n) variant (Algorithm 2) with constant 11 (Theorem 1.2), and a near-linear graphical-TSP algorithm (Algorithm 3) with constant 4 using multiplicity predictions (Theorem 1.3). It also proves a lower bound showing that some linear dependence on η is necessary under P≠NP. The metric-TSP analysis uses a prediction-biased MST plus T-join/matching arguments, with case analyses in Section 4.2; the lower bound reduces from 123/122-inapproximability.

Significance. If the results hold, this is a valuable and timely contribution: it provides the first explicit theoretical guarantee for converting heatmaps into TSP tours, with a clean, parameter-free dependence on prediction error and a matching necessity result. Theorems 1.1 and 1.2 appear technically sound: the proofs of Lemmas 4.4–4.9 and Theorem 4.3 are checkable and use standard tools (MST exchange property, Christofides, Goemans–Williamson), and no parameter is fitted in the theory. The lower bound in Theorem 7.1 is a convincing reduction from known inapproximability. However, the proof of Theorem 1.3, a headline contribution, contains an internal algebraic gap, and the Euclidean near-linear claim in Section 5 uses a matching approximation factor that is inconsistent with the analysis behind Theorem 1.2. These issues are local but load-bearing; the central metric-TSP contribution remains credible and the graphical-TSP result may be repairable.

major comments (2)

[Section 6.1, proof of Theorem 1.3] The final chain does not imply the stated bound. From Eq. (8) and Observations 6.3–6.5 the proof obtains w(T)+w(J) ≤ (w(X*∩T)+η) + 2(η+w(H−)) + (w(X*−T)+w(H+)) = w(X*) + 3η + 2w(H−) + w(H+). With η = w(H+)+w(H−), this becomes w(X*) + 4w(H+) + 5w(H−), which is not ≤ w(X*) + 4η unless w(H−)=0. The displayed inequalities support at best w(X*) + 5η after maximizing over the split of η. Since Theorem 1.3 is a headline result, the 4η guarantee needs a new or corrected argument; the current proof does not establish it.
[Section 5, Euclidean TSP] The Euclidean implementation replaces the exact/2-approximate matching used in Theorem 1.2 with the Varadarajan–Agarwal (1+ε)-approximation and sets ε=2, i.e. a 3-approximation. The proof of Theorem 1.2 (Lemma 4.6, |S|>2 case) relies on J being a 2-approximation; with a 3-approximation the constants change and the stated 11η bound is not retained. Setting ε=1 would restore the 2-approximation while keeping near-linear time, so this is fixable, but as written the claim that the running time of the Theorem 1.2 algorithm is improved while preserving its guarantee is not justified.

minor comments (5)

[Section 6] The notation is inconsistent between X* (ground set), X̄* (multiset), and the multiset operations in Observations 6.3–6.5 and the proof of Theorem 1.3. This confusion likely contributes to the proof gap; the authors should define clearly whether each expression is a set or multiset and verify the inclusion arguments in that notation.
[Observation 6.3] In the proof of the inclusion X*−T ⊆ (P−T)+H−, the multiplicity of an edge on the left is written as min{mX*(e)−mT(e), mP(e)}; it should be max{mX*(e)−mT(e), 0}. This appears to be a typo, but it should be corrected for clarity.
[Appendix C.2, SoftDist] The normalization formula defines ¯w(e) := w(e)/max_{e′∈E} w(w); the denominator should be w(e′).
[Table 3] Several GNNGLS rows on larger instances contain repeated tour-length values across different columns (e.g., 63113 and 35516), suggesting a data-reporting or alignment issue. The authors should double-check these entries.
[Section 5] The sentence 'Theorem 1.1 holds in this setting as stated' requires care: in Euclidean TSP the complete graph and its edge weights are not explicitly given, so Algorithm 1 must compute weights on the fly. This is presumably standard, but it should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the TSP guarantees follow from classical MST/matching/Christofides arguments; self-citations are explicitly non-load-bearing, and the Theorem 1.3 algebraic gap is a correctness concern, not circularity.

full rationale

I walked the derivation chain for Theorems 1.1, 1.2, A.1, and 1.3. The central metric-TSP proof (Section 4.1) is self-contained: Algorithm 1 builds an MST T with respect to a 0/1-biased weight w′, then takes a minimum S-join J with respect to the original weights. Lemma 4.4 bounds w(T\P) by w(H−) using the fact that P∪H− contains the tour X* and is connected under w′-weights; Lemma 4.5 bounds w(J) by exhibiting the explicit S-join J′ = X*ΔT. The final sum is w(X*) + 2w(H+) + 2w(H−) = w(X*) + 2η. All ingredients are classical (Christofides, Edmonds–Johnson matching, MST exchange, shortcutting under triangle inequality) and none of the lemmas assumes the target inequality. The near-linear algorithm in Section 4.2 replaces exact matching with a 2-approximation by Goemans–Williamson; Lemma 4.6 bounds the extra cost purely in terms of H+ and H− via a case analysis on the lightest tour edge. Again the bound is derived, not assumed. The Euclidean and graphical-TSP extensions follow the same pattern. The only self-citations are to Antoniadis, Eliáš, Polak, and Venzin, and they are explicitly non-load-bearing: Remark 4.1 says 'We have to disregard the prediction P when computing J' and notes that the cited approach would fail, and Remark 6.1 says 'We cannot use their analysis'. Thus no self-citation chain is used to justify the central claim. The skeptical observation about Theorem 1.3 is a real internal algebra issue: the displayed chain w(T)+w(J) ≤ (w(X*∩T)+η) + 2(η+w(H−)) + (w(X*−T)+w(H+)) evaluates to w(X*) + 3η + 2w(H−) + w(H+), i.e., w(X*) + 5w(H−) + 4w(H+), not ≤ w(X*)+4η unless w(H−)=0. This is a correctness or proof-gap concern, not a circularity: the claimed bound does not reduce to its input by definition or by construction, and no fitted parameter is renamed as a prediction. Accordingly, the circularity score is 0.

Assumptions & free parameters 4 free parameters · 8 assumptions · 0 invented entities

All axioms are classical theorems or explicit domain restrictions. The theory contains no fitted parameters; the only hand-chosen constants (k=n, 30 samples, SoftDist temperature, p=0.9, ε) appear in the experimental section and never enter the proofs. The 'prediction' P and 'heatmap' p are standard inputs in the learning-augmented model, not invented entities.

free parameters (4)

SoftDist temperature τ = chosen per instance size 'with guidance from the original paper' (Appendix C.2)
Sets heatmap quality in the SoftDist baseline; has no effect on the theorems.
k (number of sampled/top edges for Alg1/Alg1Top) = k = n
Experimental choice for extracting the edge subset P from a heatmap; theorems hold for any P.
Number of samples for Alg1 = 30 samples
Averages over sampling randomness in experiments; not load-bearing for the guarantee.
Synthetic predictor probability p and noise ε = p = 0.9 for predicted edges; ε ∈ [0,1] for noise (Appendix C.2)
Controls the synthetic-prediction experiments (Figure 8); no dependence in the proofs.

assumptions (8)

domain assumption Edge weights satisfy the triangle inequality (metric TSP).
Section 1, Theorem 1.1; used by the short-cutting step and all lemmas. Appendix B.3 shows the premise is necessary.
standard math Kruskal's algorithm correctness and the MST exchange property.
Used in Lemma 4.4 / Lemma 4.8 to compare w'(T) with the candidate connected graph P ∪ H−.
standard math Minimum-weight S-join / perfect matching is polynomial-time solvable (Edmonds–Johnson, Gabow); Goemans–Williamson gives a 2-approximation in near-linear time.
Algorithm 1 calls the exact matching; Algorithms 2–3 use the 2-approximation. Standard cited results.
standard math Short-cutting an Eulerian multigraph in a metric graph yields a Hamiltonian cycle of no greater weight.
Cited as Traub & Vygen Lemma 1.7; used in every theorem.
standard math Delaunay triangulation contains a Euclidean MST; the P∪D MST property (Proposition 5.2).
Section 5; needed for near-linear Euclidean running time.
standard math Varadarajan–Agarwal gives a (1+ε)-approximation to Euclidean min-weight perfect matching in polylog time.
Section 5; used with ε = 2 for the Euclidean version of Algorithm 2.
standard math Metric TSP is NP-hard to approximate within 123/122 (Karpinski et al. 2015).
Section 7 lower bound construction relies on this inapproximability result.
domain assumption P ≠ NP.
Used for the lower bound of Theorem 7.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of TSP with Predictions: Heatmap to Tour with Provable Guarantees." pith.science (2026). https://pith.science/paper/SRTOL65W

@misc{pith2026260703791,
  author       = {Pith},
  title        = {Pith review of: TSP with Predictions: Heatmap to Tour with Provable Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRTOL65W}},
  note         = {Machine review of arXiv:2607.03791}
}

abstract

The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of algorithms with predictions, our results can be described as $(1+2\frac{\eta}{\mathrm{OPT}})$-approximation algorithms, where $\eta$ denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.

Figures

Figures reproduced from arXiv: 2607.03791 by the authors.

**Figure 2.** Partition of J ′ = X∗∆T together with the bound on each part. In particular, we have w(T \X∗ ) ≤ w(H+) + w(H−), w((X∗ \ T) \ P) ≤ w(H−), and w((Y ∗ \ T) ∩ P) ≤ w(T \ Y ∗ ). are used in the bound w((Y ∗ \ T) ∩ P) ≤ w(T \ Y ∗ ). However, this bound is not yet sufficient to prove Lemma 4.6. We need to bound w((X∗ \ T) ∩ P) instead, and there might be e ∗ missing on the left- or right-hand side. We need to consider seve… view at source ↗

**Figure 3.** Illustration of Lemma 4.8 The following lemma holds for an arbitrary S but we will need it only for |S| = 2. Lemma 4.9. One has w(J ′ ) ≤ w(X∗ \ T) + w(H+) + w(H−). Proof. We have w(J ′ ) = w(X∗ \ T) + w(T \ X∗ ). Since T \ X∗ = ((T \ X∗ ) ∩ P) ∪ ((T \ X∗ ) \ P) ⊆ H+ ∪ (T \ P), we get w(J ′ ) ≤ w(X∗ \ T) + w(H+) + w(T \ P) Lem. 4.8.(1) ≤ w(X∗ \ T) + w(H+) + w(H−). Consider next the case |S| > 2. In this case, J is o… view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: T and the new spanning tree T ′ containing Y ∗ ∩ P. Observation 4.12. We have w((Y ∗ \ T) ∩ P) ≤ w(T \ Y ∗ ). Proof. Consider the spanning tree T ′ created by adding some edges of T to Y ∗ ∩ P (which is a forest). This way, T ′ \ T = (Y ∗ ∩ P) \ T = (((Y ∗ ∩ T) ∩ P) ∪ …

**Figure 5.** Figure 5: Solution of a graphical TSP. Only the edges used by the optimal TSP tour are drawn, you can [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]

**Figure 6.** Figure 6: Bounding the weight of the reference T-join [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]

**Figure 7.** Figure 7: Parts of J ′ and the bounds on their weight. 6.1 Analysis of Algorithm 3 We denote X¯ ∗ the multiset of edges, where each edge is contained in X¯ ∗ as many times as it is traversed by the optimal tour. On the other hand, we denote X∗ the ground set of X¯ ∗ containing a…

**Figure 8.** Figure 8: Optimality gap (the lower the better) of Christofides and our algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]

**Figure 9.** Figure 9: Visual representation of the performances of different solution search methods on DIFUSCO: [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]

**Figure 10.** Figure 10: Tightness of our analysis with respect to the dependence on false positives. Path from [PITH_FULL_IMAGE:figures/full_fig_p027_10.png]

**Figure 11.** Figure 11: Tightness of our analysis with respect to the dependence on false negatives. The optimal tour [PITH_FULL_IMAGE:figures/full_fig_p028_11.png]

**Figure 12.** Figure 12: Bad example for the doubling-tree-inspired variant. Both the left-hand side and the right-hand [PITH_FULL_IMAGE:figures/full_fig_p029_12.png]

**Figure 13.** Figure 13: Example showing that Algorithm 1 replacing the optimal odd(T)-join with a 2-approximation does not work. The graph G consists of all edges drawn in the picture regardless of color and solid/dashed/dotted style. The edges of the two copies of K5 on both sides have all …

**Figure 14.** Figure 14: Comparative analysis of edge selection strategies using SoftDist predictions. We compare the [PITH_FULL_IMAGE:figures/full_fig_p032_14.png]

**Figure 15.** Figure 15: Average performance (gap percentage) of Christofides, G2, and [PITH_FULL_IMAGE:figures/full_fig_p033_15.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 1 linked inside Pith

[1]

For G1,G2, and BS we normalize the scores by the edge costs, as is standard in this line of work [see, e.g., Sun and Yang, 2023]

An additional detail concerns normalization with respect to edge weights. For G1,G2, and BS we normalize the scores by the edge costs, as is standard in this line of work [see, e.g., Sun and Yang, 2023]. ForCHR+, we do not apply this normalization. The reason is that our algorithm does not rely on heatmaps alone to construct a feasible solution, but expli...

2023
[2]

This shows that the approximation guarantee for Algorithm 1 as stated in theorems 1.1 and A.1 is tight up to the factor k k+1 which can be arbitrarily close to 1 askincreases

+ 2 + 1 =w(X ∗) + 2k=w(X ∗) + 2 k k+ 1 η. This shows that the approximation guarantee for Algorithm 1 as stated in theorems 1.1 and A.1 is tight up to the factor k k+1 which can be arbitrarily close to 1 askincreases. B.2 Justification of the steps performed by our algorithms B.2.1 DoublingTinstead ofodd(T)-join TheexampleinFigure12showsthatif,inAlgorithm...

2024
[5]

Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli

URL https://proceedings.neurips.cc/paper/2021/hash/ 5616060fb8ae85d93f334e7267307664-Abstract.html. Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. BQ-NCO: bisim- ulation quotienting for efficient neural combinatorial optimization. InAdvances in Neural In- formation Processing Systems 36: Annual Conference on Neural Informa...

2021
[8]

HaroldN.Gabow.Implementationofalgorithmsformaximummatchingonnonbipartitegraphs.PhDthesis, Stanford University, USA,

doi: 10.1609/AAAI.V35I8.16916. HaroldN.Gabow.Implementationofalgorithmsformaximummatchingonnonbipartitegraphs.PhDthesis, Stanford University, USA,

doi:10.1609/aaai.v35i8.16916
[10]

Keld Helsgaun

doi: 10.25080/TCWV9851. Keld Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic.Eur. J. Oper. Res., 126(1):106–130, 2000.doi: 10.1016/S0377-2217(99)00284-2. Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. InThe Tenth Inte...

doi:10.25080/tcwv9851
[12]

At the end, we would receive a tourX with weight w(X) = 2w(X ∗)−3 as argued in Section B.2.1

There, the cheapestodd(T)-join with respect to the weightsw′ would beT itself with w′(T) = 0 . At the end, we would receive a tourX with weight w(X) = 2w(X ∗)−3 as argued in Section B.2.1. B.2.3 Optimalodd(T)-join in Algorihtm 1 cannot be replaced by a 2-approximation InFigure13,weshowaninputgraphwhichshowsthatAlgorithm1,ifusinga2-approximate odd(T)-join ...

1976
[13]

doi: 10.1007/S10601-022-09327-Y. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. InSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 32–45. ACM, 2021.doi: 10.1145/3406325.3451009. Richard M. Karp. Reducibility among combinatorial problems. InProceedings of a sympos...

arXiv 2021
[15]

22 Vladimir Kolmogorov

URLhttp: //papers.nips.cc/paper_files/paper/2022/hash/0cddb777d3441326544e21b67f41bdc8- Abstract-Conference.html. 22 Vladimir Kolmogorov. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43–67, 2009.doi: 10.1007/s12532-009-0002-8. Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon,...

doi:10.1007/s12532-009-0002-8 2022

Show all 35 references

[17]

YangLi,JinpeiGuo,RunzhongWang,HongyuanZha,andJunchiYan

URL https://proceedings.neurips.cc/paper/2021/hash/ 29539ed932d32f1c56324cded92c07c2-Abstract.html. YangLi,JinpeiGuo,RunzhongWang,HongyuanZha,andJunchiYan. FastT2T:optimizationconsistency speeds up diffusion-based training-to-testing solving for combinatorial optimization. InA...

2021
[19]

Zijun Liao, Jinbiao Chen, Debing Wang, Zizhen Zhang, and Jiahai Wang

URLhttps://openreview.net/forum?id=grU1VKEOLi. Zijun Liao, Jinbiao Chen, Debing Wang, Zizhen Zhang, and Jiahai Wang. BOPO: neural combinatorial optimization via best-anchored and objective-guided preference optimization. InForty-second Inter- national Conference on Machine Lea...

2025
[22]

23 Mingjun Pan, Guanquan Lin, You-Wei Luo, Bin Zhu, Zhien Dai, Lijun Sun, and Chun Yuan

doi: 10.1017/9781108637435.037. 23 Mingjun Pan, Guanquan Lin, You-Wei Luo, Bin Zhu, Zhien Dai, Lijun Sun, and Chun Yuan. Preference optimization for combinatorial optimization problems. InForty-second International Conference on Machine Learning, ICML 2025, Proceedings of Mach...

2025 doi
[23]

URL https://openreview.net/forum?id=yEwakMNIex

OpenReview.net, 2025b. URL https://openreview.net/forum?id=yEwakMNIex. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Sys...

2018
[24]

neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html

URLhttps://proceedings. neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html. Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combina- torial optimization problems. InAdvances in Neural Information Processing Systems 35:...

2018
[25]

Gerhard Reinelt

URLhttp: //papers.nips.cc/paper_files/paper/2022/hash/a3a7387e49f4de290c23beea2dfcdc75- Abstract-Conference.html. Gerhard Reinelt. TSPLIB - A traveling salesman problem library.INFORMS J. Comput., 3(4):376–384, 1991.doi: 10.1287/IJOC.3.4.376. Daniel J. Rosenkrantz, Richard Edw...

2022 doi
[26]

Anatoliy

doi: 10.1145/321958.321975. Anatoliy. I. Serdyukov. Some extremal bypasses in graphs.Upravliaemie Systemy, 17:76–79,
[28]

Vera Traub and Jens Vygen.Approximation Algorithms for Traveling Salesman Problems

URLhttp://papers.nips.cc/paper_files/ paper/2023/hash/0ba520d93c3df592c83a611961314c98-Abstract-Conference.html. Vera Traub and Jens Vygen.Approximation Algorithms for Traveling Salesman Problems. Cambridge University Press,

2023
[31]

HaoranYe,JiaruiWang,HelanLiang,ZhiguangCao,YongLi,andFanzhangLi.GLOP:learningglobalpar- titionandlocalconstructionforsolvinglarge-scaleroutingproblemsinreal-time

URL https://openreview.net/forum?id=cEJ9jNJuJP. HaoranYe,JiaruiWang,HelanLiang,ZhiguangCao,YongLi,andFanzhangLi.GLOP:learningglobalpar- titionandlocalconstructionforsolvinglarge-scaleroutingproblemsinreal-time. InThirty-EighthAAAI Conference on Artificial Intelligence, AAAI 20...

2024
[34]

In our experiments, we made the following choices

proposes two pre-trained models: one trained on instances of variablesizeandanothertrainedonlargecaseswith n= 200 nodes.Theyalsointroducetwodecod- ing strategies: an autoregressive (AR) decoder and a non-autoregressive (NAR) decoder, where the edge probabilities are predicted ...

2022
[36]

While our theoretical analysis is developed for Alg1, we evaluate the three approaches

Since this latter approach is essentially Christofides’ algorithm applied to a modified graph, we denote it asCHR+. While our theoretical analysis is developed for Alg1, we evaluate the three approaches. In all cases, we setk=n . Under the Alg1 approach, we generate 30 distinc...

1910
[1973]

Michel X

URLhttps://searchworks.stanford.edu/view/2168982. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems.SIAMJ.Comput.,24(2):296–317,1995. doi: 10.1137/S0097539793242618 . Announced at SODA

1995
[1976]

The traveling salesman problem on a graph and some related integer polyhedra.Math

Gérard Cornuéjols, Jean Fonlupt, and Denis Naddef. The traveling salesman problem on a graph and some related integer polyhedra.Math. Program., 33(1):1–27, 1985.doi: 10.1007/BF01582008. Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. F...

1985 doi
[1978]

Closest-point problems

Michael Ian Shamos and Dan Hoey. Closest-point problems. In16th Annual Symposium on Foundations of Computer Science, 1975, pages 151–162. IEEE Computer Society, 1975.doi: 10.1109/SFCS.1975.8. Zhiqing Sun and Yiming Yang. DIFUSCO: graph-based diffusion solvers for combinatorial...

1975 doi
[1999]

URLhttp://dl.acm.org/citation.cfm?id=314500. 314918. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. InAdvances in Neural In- formation Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 2692–2700,

2015
[2006]

URL http://www.jstor.org/stable/j.ctt7s8xg

ISBN 9780691129938. URL http://www.jstor.org/stable/j.ctt7s8xg. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.J. ACM, 45(5):753–782, 1998.doi: 10.1145/290179.290180. Evripidis Bampis, Bruno Escoffier, Dimitri...

1998
[2008]

doi: 10.1007/978-3-540-77974-2

ISBN 978-3-540-77973-5. doi: 10.1007/978-3-540-77974-2. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh PA Management Sciences Research Group,

doi
[2015]

24 Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian

URL https://proceedings.neurips.cc/paper/2015/hash/ 29921001f2f04bd3baee84a12e98098f-Abstract.html. 24 Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling s...

2015
[2017]

neurips.cc/paper/2017/hash/d9896106ca98d3d05b8cbdf4fd8b13a1-Abstract.html

URLhttps://proceedings. neurips.cc/paper/2017/hash/d9896106ca98d3d05b8cbdf4fd8b13a1-Abstract.html. MinsuKim,JinkyooPark,andJounghoKim. LearningcollaborativepoliciestosolveNP-hardroutingprob- lems. InAdvancesinNeuralInformationProcessingSystems34:AnnualConferenceonNeuralInforma...

2017
[2018]

COExpander: Adaptive solution expansion for combinatorial optimization

Jiale Ma, Wenzheng Pan, Yang Li, and Junchi Yan. COExpander: Adaptive solution expansion for combinatorial optimization. InForty-second International Conference on Machine Learning, ICML 2025, Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025a. URLhttps: //...

2025
[2019]

org/abs/1906.01227

URLhttp://arxiv. org/abs/1906.01227. ChaitanyaK.Joshi,QuentinCappart,Louis-MartinRousseau,andThomasLaurent. Learningthetravelling salesperson problem requires rethinking generalization.Constraints An Int. J., 27(1-2):70–98,

1906 arXiv
[2020]

Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon

URLhttps://proceedings.neurips.cc/paper/2020/hash/ f231f2107df69eab0a3862d50018a9b2-Abstract.html. Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. InAdvances in Neural Informati...

2020
[2021]

20 Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.Computational Geometry: Algorithms and Applications

doi: 10.1016/J.EJOR.2020.07.063. 20 Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.Computational Geometry: Algorithms and Applications. Springer Berlin Heidelberg, 3 edition,

2020 doi
[2023]

Darko Drakulic, Sofia Michel, and Jean-Marc Andreoli

URL http://papers.nips.cc/paper_files/paper/2023/hash/ f445ba15f0f05c26e1d24f908ea78d60-Abstract-Conference.html. Darko Drakulic, Sofia Michel, and Jean-Marc Andreoli. GOAL: A generalist combinatorial optimization agent learner. InThe Thirteenth International Conference on Lea...

2023
[2024]

Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, and Junchi Yan

URLhttp://papers.nips.cc/paper_files/paper/2024/ hash/352b13f01566ae34affacc60e98c16af-Abstract-Conference.html. Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, and Junchi Yan. Unify ML4TSP: drawing methodological principles for TSP and beyond from str...

2024
[2025]

Ran Duan, Seth Pettie, and Hsin-Hao Su

URLhttps://openreview.net/forum?id=z2z9suDRjw. Ran Duan, Seth Pettie, and Hsin-Hao Su. Scaling algorithms for weighted matching in general graphs. ACM Trans. Algorithms, 14(1):8:1–8:35, 2018.doi: 10.1145/3155301. Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the...

2018 doi
[2026]

Competitive caching with machine learned advice.J

Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.J. ACM, 68(4):24:1–24:25, 2021.doi: 10.1145/3447579. Announced at ICML

2021 doi

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

For G1,G2, and BS we normalize the scores by the edge costs, as is standard in this line of work [see, e.g., Sun and Yang, 2023]

An additional detail concerns normalization with respect to edge weights. For G1,G2, and BS we normalize the scores by the edge costs, as is standard in this line of work [see, e.g., Sun and Yang, 2023]. ForCHR+, we do not apply this normalization. The reason is that our algorithm does not rely on heatmaps alone to construct a feasible solution, but expli...

2023

[2] [2]

This shows that the approximation guarantee for Algorithm 1 as stated in theorems 1.1 and A.1 is tight up to the factor k k+1 which can be arbitrarily close to 1 askincreases

+ 2 + 1 =w(X ∗) + 2k=w(X ∗) + 2 k k+ 1 η. This shows that the approximation guarantee for Algorithm 1 as stated in theorems 1.1 and A.1 is tight up to the factor k k+1 which can be arbitrarily close to 1 askincreases. B.2 Justification of the steps performed by our algorithms B.2.1 DoublingTinstead ofodd(T)-join TheexampleinFigure12showsthatif,inAlgorithm...

2024

[3] [5]

Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli

URL https://proceedings.neurips.cc/paper/2021/hash/ 5616060fb8ae85d93f334e7267307664-Abstract.html. Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. BQ-NCO: bisim- ulation quotienting for efficient neural combinatorial optimization. InAdvances in Neural In- formation Processing Systems 36: Annual Conference on Neural Informa...

2021

[4] [8]

HaroldN.Gabow.Implementationofalgorithmsformaximummatchingonnonbipartitegraphs.PhDthesis, Stanford University, USA,

doi: 10.1609/AAAI.V35I8.16916. HaroldN.Gabow.Implementationofalgorithmsformaximummatchingonnonbipartitegraphs.PhDthesis, Stanford University, USA,

doi:10.1609/aaai.v35i8.16916

[5] [10]

Keld Helsgaun

doi: 10.25080/TCWV9851. Keld Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic.Eur. J. Oper. Res., 126(1):106–130, 2000.doi: 10.1016/S0377-2217(99)00284-2. Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. InThe Tenth Inte...

doi:10.25080/tcwv9851

[6] [12]

At the end, we would receive a tourX with weight w(X) = 2w(X ∗)−3 as argued in Section B.2.1

There, the cheapestodd(T)-join with respect to the weightsw′ would beT itself with w′(T) = 0 . At the end, we would receive a tourX with weight w(X) = 2w(X ∗)−3 as argued in Section B.2.1. B.2.3 Optimalodd(T)-join in Algorihtm 1 cannot be replaced by a 2-approximation InFigure13,weshowaninputgraphwhichshowsthatAlgorithm1,ifusinga2-approximate odd(T)-join ...

1976

[7] [13]

doi: 10.1007/S10601-022-09327-Y. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. InSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 32–45. ACM, 2021.doi: 10.1145/3406325.3451009. Richard M. Karp. Reducibility among combinatorial problems. InProceedings of a sympos...

arXiv 2021

[8] [15]

22 Vladimir Kolmogorov

URLhttp: //papers.nips.cc/paper_files/paper/2022/hash/0cddb777d3441326544e21b67f41bdc8- Abstract-Conference.html. 22 Vladimir Kolmogorov. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43–67, 2009.doi: 10.1007/s12532-009-0002-8. Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon,...

doi:10.1007/s12532-009-0002-8 2022