{"id":"0074d419-e9ce-45e0-9ee5-ed9d643364c9","arxiv_id":"2607.03791","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"A Christofides-style algorithm with prediction-biased spanning trees turns any TSP edge heatmap into a tour of cost at most OPT + 2η, with near-linear-time and graphical variants plus a matching lower bound.","lead":"This paper gives the first provable guarantee for converting a machine-learned edge 'heatmap' into an actual traveling-salesperson tour: the tour length is at most the optimum plus twice the weighted error of the heatmap. It also gives near-linear-time and graph variants, and shows the linear dependence on error is unavoidable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.3's final inequality does not follow: the proof derives OPT + 5w(H−) + 4w(H+), not OPT + 4η, so the 4η graphical-TSP guarantee is unsupported as written.","rationale":"The reader's weakest-assumption analysis focused on metric triangle inequality and found the mathematical core sound. My read of the proof of Theorem 1.3 disagrees on that point: the final algebra in the graphical-TSP analysis does not close. I did not find a comparable gap in the proof of Theorem 1.1; the core Christofides-style argument appears sound, and the lower bound also checks out. However, Theorem 1.3 is one of the paper's three central results, and its stated 4η guarantee is not established by the written derivation. The concern is concrete and internal: a purely algebraic substitution from the paper's own displayed inequalities yields OPT + 5w(H−) + 4w(H+), not OPT + 4η. This should be corrected or explicitly addressed before publication. The severity is conditional rather than outright rejection because the theorem may be repairable by a different argument or a corrected constant, and the paper's other main contributions appear intact. Credit is due for the genuine and well-executed core of Algorithm 1/Theorem 1.1, the linear lower bound, and the empirical disclosure of CHR+ versus Algorithm 1; none of those erase the gap in Theorem 1.3's proof.","tokens_in":38283,"tokens_out":46102,"duration_ms":459909,"concrete_test":"Run a small exhaustive search over all connected graphs on n ≤ 6 vertices with unit or small integer weights, all optimal Eulerian tours X*, and all multisets P ⊆ X* (false negatives only, then also with false positives). For each case, compute Algorithm 3's output and compare to w(X*) + 4η. If any case exceeds the bound, Theorem 1.3 is false as stated. Independently, recompute the final displayed inequality of Theorem 1.3 substituting η = w(H+)+w(H−): the derived expression is w(X*)+5w(H−)+4w(H+), which exceeds the claimed bound whenever w(H−)>0. This analytical check alone shows the proof needs a missing argument or a corrected constant.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 1.3 (Section 6.1), the paper combines Lemma 6.2, Observation 6.3, Observation 6.4, and Observation 6.5 into the final chain:\n\nw(T)+w(J) ≤ (w(X*∩T)+η) + 2(η+w(H−)) + (w(X*−T)+w(H+)).\n\nSince X* = (X*∩T) ∪ (X*−T), this equals w(X*) + 3η + 2w(H−) + w(H+). Substituting η = w(H−) + w(H+) gives w(X*) + 5w(H−) + 4w(H+), which is not ≤ w(X*) + 4η unless w(H−) = 0. Thus the paper's stated bound ≤ w(X*)+4η does not follow from its own inequalities.\n\nThis is not a loose-constant issue or an external-consensus disagreement; it is an internal algebraic gap in a central stated theorem. The 4η guarantee for graphical TSP with multiplicity predictions is a headline contribution (Theorem 1.3), and the proof as written does not establish it. The same issue affects the summary around Figure 6 and the 'Summarizing' paragraph. A repair may exist, but it is not present in the manuscript.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":112,"tokens_out":11367,"duration_ms":298479,"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":[{"comment":"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":"Section 6.1, proof of Theorem 1.3"},{"comment":"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.","section":"Section 5, Euclidean TSP"}],"minor_comments":[{"comment":"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.","section":"Section 6"},{"comment":"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.","section":"Observation 6.3"},{"comment":"The normalization formula defines ¯w(e) := w(e)/max_{e′∈E} w(w); the denominator should be w(e′).","section":"Appendix C.2, SoftDist"},{"comment":"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":"Table 3"},{"comment":"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.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The core metric-TSP results (Theorems 1.1 and 1.2) and the lower bound are sound and make a solid contribution. My main concern is the graphical TSP theorem: the proof of Theorem 1.3 has a concrete algebraic gap, and the final bound does not follow from the displayed inequalities. I would like the authors to either supply a correct proof of the 4η bound or adjust the theorem to the bound that the proof actually supports (5η). The Euclidean matching factor issue in Section 5 is easy to repair. I recommend major revision, with the acceptability threshold being a rigorous fix of Theorem 1.3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nOverall, 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.","headline":"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−).","tokens_in":39199,"tokens_out":7092,"would_cite":true,"duration_ms":67917,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["TSP","algorithms with predictions","learning-augmented algorithms","heatmap","minimum spanning tree and matching heuristic","metric TSP","graphical TSP","approximation guarantee"],"falsifier":"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$.","tokens_in":1465,"feed_emoji":"🗺️","tokens_out":2140,"duration_ms":63776,"temperature":0.7,"texified_at":"2026-08-05T21:14:39.604467+00:00","pith_summary":"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$).","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":6626,"prompt_tokens":793,"completion_tokens":5833,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":793,"completion_tokens_details":{"reasoning_tokens":5040}},"feed_headline":"Heatmaps become provable TSP tours: cost ≤ optimum plus 2η","feed_subtitle":"Given a heatmap of likely tour edges, the computed tour stays within twice the heatmap's weighted error of optimal.","key_machinery":"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$.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["TSP tours from heatmaps: guarantee within 2η of optimal","Predictive TSP: heatmap errors bounded by 2η approximation","MST+matching turns heatmaps into tours with provable TSP guarantee","Heatmap-guided TSP: approximation ratio tied to prediction loss"],"cache_read_input_tokens":40320,"weakest_assumption_plain":"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).","fun_headline_variants_meta":{"raw":{"variants":["TSP tours from heatmaps: guarantee within 2η of optimal","Predictive TSP: heatmap errors bounded by 2η approximation","MST+matching turns heatmaps into tours with provable TSP guarantee","Heatmap-guided TSP: approximation ratio tied to prediction loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00078,"raw_usage":{"total_tokens":3267,"prompt_tokens":714,"completion_tokens":2553,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":2475}},"tokens_in":458,"tokens_out":2553,"duration_ms":16239,"temperature":1.0,"reasoning_tokens":2475,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T08:47:29.078481+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":2}