I am happy to announce that our paper “TSP with predictions: heatmap to tour with provable guarantees”, co-authored with Marek Elias, Fabrizio Grandoni, Adam Polak, has been accepted as a regular paper at ICML 2026.

In this work, we study how machine learning predictions can be used to improve algorithmic performance for the Traveling Salesman Problem (TSP). In particular, we consider heatmaps produced by neural networks as predictive signals for edge selection probabilities, and we develop algorithms that transform such heatmaps into provably good tours.

Our approach comes with theoretical guarantees, showing that the resulting solutions can be interpreted within an approximation framework, where the quality depends on the discrepancy between predicted heatmaps and optimal solutions. We also complement our theoretical findings with an experimental evaluation comparing against existing prediction-based approaches.