{"ID":2828683,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.15800","arxiv_id":"2512.15800","title":"Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimization","abstract":"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.","short_abstract":"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 barcod...","url_abs":"https://arxiv.org/abs/2512.15800","url_pdf":"https://arxiv.org/pdf/2512.15800v1","authors":"[\"Ilya Trofimov\",\"Daria Voronkova\",\"Alexander Mironenko\",\"Anton Dmitriev\",\"Eduard Tulchinskii\",\"Evgeny Burnaev\",\"Serguei Barannikov\"]","published":"2025-12-16T20:04:25Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.AI\"]","methods":"[]","has_code":false}