Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimization
Not on the map. Why?
Abstract (arXiv)
We introduce a topological feedback mechanism for the Travelling Salesman Problem (TSP) by analyzing the divergence between a tour and the minimum spanning tree (MST). Our key contribution is a canonical decomposition theorem that expresses the tour-MST gap as edge-wise topology-divergence gaps from the RTD-Lite barcode. Based on this, we develop a topological guidance for 2-opt and 3-opt heuristics that increases their performance. We carry out experiments with fine-optimization of tours obtained from heatmap-based methods, TSPLIB, and random instances. Experiments demonstrate the topology-guided optimization results in better performance and faster convergence in many cases.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 11 of its 20 references that are in the map. First posted on arXiv 16 Dec 2025.
Builds on
11 of 20 references.
References · 11
- 2015Pointer Networkscited by 895
- 2018Attention, Learn to Solve Routing Problems!cited by 656
- 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
- 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
- 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
- 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
- 2021Representation Topology Divergence: A Method for Comparing Neural Network Representationscited by 66
- 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 59
- 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 58
- 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
- 2025RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Taskscited by 4
Built on by
Not cited yet.