Pith. sign in

REVIEW 5 minor 35 references

Any edge heatmap can be turned into a TSP tour whose extra cost is at most twice the heatmap's L1 error.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-11 23:54 UTC pith:SRTOL65W

load-bearing objection Clean first learning-augmented approx for metric/graphical TSP: excess cost linear in L1 heatmap error, with tight analysis and usable experiments.

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

TSP with Predictions: Heatmap to Tour with Provable Guarantees

Marek Eli\'a\v{s} , Fabrizio Grandoni , Adam Polak , Eleonora Vercesi This is my paper
classification cs.DS cs.LG MSC 68W2590C27
keywords TSPalgorithms with predictionsheatmapChristofides algorithmapproximation algorithmsneural combinatorial optimizationmetric TSPgraphical TSP
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Neural networks often output a heatmap of edge probabilities for the Traveling Salesperson Problem, but turning those probabilities into a concrete tour has been ad-hoc and without guarantees. This paper supplies polynomial-time algorithms that take any such heatmap and produce a feasible tour whose length exceeds some reference tour by at most a constant times the L1 distance η between the heatmap and that tour. The main result is a Christofides-style procedure that runs in O(n^{3}) time and guarantees expected extra cost at most 2η; faster near-linear variants achieve constants 11 (metric) and 4 (graphical). The same algorithms work for Euclidean and sparse graphical instances, and experiments show they convert both neural and heuristic heatmaps into better tours than greedy or beam search while remaining lightweight. The point is to give the machine-learning pipeline a decoder whose approximation quality scales smoothly with prediction quality, so better heatmaps become useful rather than being drowned out by heavy search.

Core claim

There exists an O(n^{3})-time algorithm that, given any edge heatmap p with L1 error η relative to some tour X*, returns a tour X satisfying E[w(X)] ≤ w(X*) + 2η. Near-linear variants achieve the same form of guarantee with larger constants (11 for metric TSP, 4 for graphical TSP).

What carries the argument

A prediction-biased Christofides algorithm: build a minimum spanning tree whose edge weights are zeroed (or sign-flipped) on predicted edges, then complete with a minimum-weight join of the odd-degree vertices computed on the original weights, and short-cut the resulting Eulerian multigraph. The L1 error η controls the excess cost of both the tree and the join.

Load-bearing premise

The near-linear analysis assumes a case-by-case accounting for the lightest edge of the reference tour when more than two vertices have odd degree; if that case split misses a configuration of false positives and negatives, the constant 11 is no longer guaranteed.

What would settle it

Construct a family of metric instances and heatmaps whose L1 error η is positive but arbitrarily small, run the claimed O(n^{3}) algorithm, and check whether the returned tour ever exceeds the reference tour by more than 2η; any systematic excess above that bound falsifies the main theorem.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper gives learning-augmented algorithms that convert an arbitrary edge heatmap (or sampled prediction set P) into a feasible TSP tour whose excess cost is linear in the L1 prediction error η relative to some reference tour X*. For metric TSP the main result is an O(n^{3}) Christofides-style algorithm (Algorithm 1) with E[w(X)] ≤ w(X*) + 2η (Theorem 1.1 / Theorem 4.3); a near-linear variant that biases the MST toward heavy predicted edges and uses a 2-approximate join yields +11η (Theorem 1.2). Euclidean and graphical specializations improve running times further (Theorems 1.3 and the Euclidean claims). A matching-style lower bound (Theorem 7.1) shows that linear dependence on η/OPT is necessary, and Appendix B supplies tightness examples. Experiments on ML4CO and TSPLIB instances compare the practical CHR+ decoder against greedy, beam search and plain Christofides on several public neural and non-neural heatmaps.

Significance. The work fills a clear gap: despite hundreds of papers on algorithms with predictions, approximation algorithms for TSP had not been studied in this model, and the neural-combinatorial-optimization literature lacked any explicit link between heatmap quality and tour cost. The O(n^{3}) guarantee is short, clean and tight up to the constant 2; the lower bound and the counter-examples that motivate the design choices (Appendix B) strengthen the contribution. Public code and data, together with a synthetic predictor that lets one dial η, make the experimental claims reproducible. Even if the near-linear constants are not optimal, the existence of a lightweight decoder whose excess cost scales smoothly with heatmap accuracy is of both theoretical and practical interest.

minor comments (5)
  1. Abstract and Theorem 1.1 state a (1+2η/OPT) guarantee, while the body works with an arbitrary reference tour X* (not necessarily optimal). A single clarifying sentence would avoid any ambiguity.
  2. Section 4.2.1, Lemma 4.6: the three-case analysis of the lightest edge e* is correct but dense; a short roadmap sentence before the cases would help the reader.
  3. Section 8 / Appendix C: CHR+ (soft weighting w(e)(1-q(e))) is the practical decoder used in all tables, yet the theorems analyse the hard-threshold Algorithm 1. Explicitly note that the experiments evaluate a natural continuous relaxation of the analysed algorithm.
  4. Figure 8 caption and surrounding text: the horizontal axis is the synthetic noise parameter ε, not the realised L1 error η; a brief remark that ε controls η would improve readability.
  5. A few typographical slips remain (e.g., “Westudythe”, “Tosummarize”, missing spaces after periods in the introduction). A light copy-edit pass would polish the presentation.

Circularity Check

0 steps flagged

No circularity: approximation bounds are derived from first-principles analysis of a biased Christofides procedure relative to an arbitrary external reference tour X*

full rationale

The central claims (Theorems 1.1–1.3) define the prediction error η externally as the L1 (or multiset-symmetric-difference) distance between an arbitrary input heatmap/prediction P and some fixed reference tour X* of the input instance. The algorithms construct a spanning tree T biased toward P and an (approximate) odd(T)-join J, then shortcut; the proofs bound w(T)+w(J) by writing explicit reference objects (T relative to P∪H−, J′=X*ΔT) and applying the MST optimality property and triangle inequality. Lemmas 4.4–4.5 (and the analogous graphical and near-linear lemmas) therefore relate the output cost to w(X*)+O(η) by construction of the algorithm, not by redefining η or X* in terms of the output. No parameters are fitted to data inside the theorems; the experimental section merely evaluates the same algorithms on independently trained public heatmaps and a synthetic noise model whose ε is an exogenous control. Self-citations (e.g., to Antoniadis et al. 2025) are used only to contrast why a different meta-algorithm fails for metric TSP, not to justify the positive bounds. The lower-bound reduction in Section 7 is likewise external. Consequently the derivation chain is self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claims rest only on standard metric-TSP facts (triangle inequality, shortcutting of Eulerian multisets, existence of min-weight perfect matchings / T-joins) and the classical Christofides / Goemans-Williamson primitives. No free parameters are fitted; the constants 2, 11 and 4 are derived. The sole modeling choice is the definition of prediction error η as weighted L1 (or multiset symmetric difference), which is conventional in algorithms-with-predictions.

axioms (3)
  • domain assumption Edge weights satisfy the triangle inequality (metric TSP).
    Stated in Section 1 and used for shortcutting; without it the problem is inapproximable even with perfect predictions (Appendix B.3).
  • standard math A min-weight perfect matching / T-join of an even set S can be computed in polynomial (or near-linear approximate) time.
    Invoked for J in Algorithms 1–3; classical results of Edmonds-Johnson, Gabow, Goemans-Williamson.
  • standard math Shortcutting an Eulerian multiset in a metric graph yields a Hamiltonian cycle of no greater weight.
    Standard fact used at the end of every algorithm (Traub-Vygen Lemma 1.7).

pith-pipeline@v1.1.0-grok45 · 44121 in / 2390 out tokens · 18899 ms · 2026-07-11T23:54:53.910544+00:00 · methodology

0 comments
read the original 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 Adam Polak, Eleonora Vercesi, Fabrizio Grandoni, Marek Eli\'a\v{s}.

Figure 1
Figure 1. Figure 1: Example instance of a TSP where the vertices are points on a line. Only the edges of the optimal [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. 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 con… view at source ↗
Figure 3
Figure 3. 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 ca… view at source ↗
Figure 4
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) ∪ ((Y ∗ \ T) ∩ P)) \ T = (Y ∗ \ T) ∩ P, see also [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
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] view at source ↗
Figure 6
Figure 6. Figure 6: Bounding the weight of the reference T-join [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
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 all edges which are traversed by the optimal tour at least once. Lemma 6.2. w(T) ≤ w(T ∩ X∗ ) + η. Proof. Note that P ∪ H− ⊇ X∗ is a connecte… view at source ↗
Figure 8
Figure 8. Figure 8: Optimality gap (the lower the better) of Christofides and our algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
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] view at source ↗
Figure 10
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] view at source ↗
Figure 11
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] view at source ↗
Figure 12
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] view at source ↗
Figure 13
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 weight 1. P consists of all edges in the picture except for the two edges of length M/2 incident to v marked with blue-dashed line, so η = O… view at source ↗
Figure 14
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] view at source ↗
Figure 15
Figure 15. Figure 15: Average performance (gap percentage) of Christofides, G2, and [PITH_FULL_IMAGE:figures/full_fig_p033_15.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 4 canonical work pages

  1. [1]

    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, Dimitris Fotakis, Panagiotis Patsilinakos, and Michalis Xefteris. Polynomial time learn...

    doi:10.1145/290179.290180 1998

  2. [2]

    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,

    doi:10.1016/j.ejor.2020.07.063 2020

  3. [3]

    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:10.1007/978-3-540-77974-2

  4. [4]

    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. Faster matchings via learned duals. InAdvances in Neural Information Processing S...

    work page doi:10.1007/bf01582008 1985

  5. [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

  6. [6]

    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 Learning Representations, ICLR

    2023

  7. [7]

    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 Chinese postman.Math. Program., 5 (1):88–124, 1973.doi: 10.1007/BF01580113. Zha...

    work page doi:10.1145/3155301 2018

  8. [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

  9. [9]

    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

    doi:10.1137/s0097539793242618 1995

  10. [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 2000

  11. [12]

    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,

    Pith/arXiv arXiv 1906

  12. [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...

    doi:10.1007/s10601-022-09327-y 2021

  13. [14]

    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- tionProcessingSystems2021,NeurIPS2021,pages10418–10430,2021. URL https://proce...

    2017

  14. [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

  15. [16]

    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 Information Pro- cessing Systems 34: Annual Conference on Neural Information Processing S...

    2020

  16. [17]

    YangLi,JinpeiGuo,RunzhongWang,HongyuanZha,andJunchiYan

    URLhttps://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. InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural ...

    2021

  17. [18]

    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 streamlined design space of learning and search. InThe Thirteenth International Con...

    2024

  18. [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 Learning, ICML 2025, Proceedings of Machine Learning Research. PMLR / OpenReview.net,

    2025

  19. [20]

    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

    doi:10.1145/3447579 2021

  20. [21]

    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: //proceedings.mlr.press/v267/ma25r.html. Jiale Ma, Wenzheng Pan, Yang Li, and Junc...

    2025

  21. [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 Machine Learning Research. PMLR / OpenReview.net, 2025a. URLhttps://proceedings.mlr....

    work page doi:10.1017/9781108637435.037 2025

  22. [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 Systems 2018, NeurIPS 2018, pages 9684–9693,

    2018

  23. [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: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022,

    2018

  24. [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 Edwin Stearns, and Philip M. Lewis II. An analysis of several heuristics for the tr...

    doi:10.1287/ijoc.3.4.376 2022

  25. [26]

    Anatoliy

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

    doi:10.1145/321958.321975

  26. [27]

    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 optimization. InAdvances in Neural Information Processing Systems 36: Annual Co...

    work page doi:10.1109/sfcs.1975.8 1975

  27. [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

  28. [29]

    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

  29. [30]

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

    URLhttps://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 salesman problems. In Forty-first International Conference on Machine Learning, ICML

    2015

  30. [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 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligenc...

    doi:10.1609/aaai.v38i18.30009 2024

  31. [32]

    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

  32. [33]

    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

  33. [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 simultaneously. In our experiments, we made the following choices. We use only t...

    2022

  34. [35]

    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

  35. [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 distinct edge setsP for each instance to account for stochasticity; in contrast, the Al...

    arXiv 1910