TSP with Predictions: Heatmap to Tour with Provable Guarantees

Marek Elias, Fabrizio Grandoni, Adam Polak, Eleonora Vercesi
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:27861-27890, 2026.

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\eta/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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-elias26a, title = {{TSP} with Predictions: Heatmap to Tour with Provable Guarantees}, author = {Elias, Marek and Grandoni, Fabrizio and Polak, Adam and Vercesi, Eleonora}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {27861--27890}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/elias26a/elias26a.pdf}, url = {https://proceedings.mlr.press/v306/elias26a.html}, 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\eta/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.} }
Endnote
%0 Conference Paper %T TSP with Predictions: Heatmap to Tour with Provable Guarantees %A Marek Elias %A Fabrizio Grandoni %A Adam Polak %A Eleonora Vercesi %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-elias26a %I PMLR %P 27861--27890 %U https://proceedings.mlr.press/v306/elias26a.html %V 306 %X 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\eta/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.
APA
Elias, M., Grandoni, F., Polak, A. & Vercesi, E.. (2026). TSP with Predictions: Heatmap to Tour with Provable Guarantees. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:27861-27890 Available from https://proceedings.mlr.press/v306/elias26a.html.

Related Material