- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces an improvement heuristic for TSP solvers. The core idea is to use an edge-wise topological divergence measurement over the decompositional gap between a TSP tour and the minimum spanning tree, then the larger divergence will be used for local search.
Critical strengths
-
The paper introduces a novel heuristic of topological data analysis in combinatorial optimization.
-
The theoretical analysis is valuable for an interpretable signal of guiding local search.
-
The paper introduces extensive experiments and shows reasonable improvements.
Critical weaknesses
-
The LKJ results are promising. However, in the abstract and main body of the paper, the reported aggregated speedup is 24.1%, but in Appendix U, it is 21.4%.
-
The L2C integration results show very incremental improvement over small and moderate-sized instances, not to mention that the instances are synthetic instances. It would be great to see some comparison with other inexpensive region-selection strategies such as prioritizing long tour edges, high local costs, or different types of geometric measures.
-
The abstract is cherry-picking the results. The abstract says that p is smaller than 10^{-3} but in Table 3 for the 2000-node instance, p is 0.028.
-
The paper mentioned multiple times that the work is applicable to ATSP and HCP setting but the experiements largely reduce the problem to symmetric setting and use the same optimization methods. More evidence on how the proposed methods can be used for fundamentally different combinatorial optimization problems instead of symmetric TSP need to provided.
Questions for authors
Please see weakness and addresses the questions there.
3 comments
It is good to see that the typos are fixed, and the claims are more accurate. The additional experiments are helpful. But the issue claimed contribution with the previous results remain the same.
Response
We thank the Reviewer for verifying the corrections. Regarding the remaining concern that the contribution over previous results is incremental, we make the delta precise:
-
Versus the strongest previous results. Heatmap-based neural solvers (DIFUSCO, SoftDist, DIMES, UTSP, ATT-GCN): RTDL-enhanced post-processing shortens tours on every instance (, win rates 70-99%) and cuts post-processing wall-clock by up to ~14× at (n=) (DIMES: 112.7h → 8.0h, Table 4) - with pretrained checkpoints. Against NeuroLKH (leading learned candidate model): faster in 180/180 matched-budget paired runs, ~18% better average tour length on hard (n=1000-5000) instances, under both uniform and mixed training. Against FastT2T post-processing: shorter tours and ~2× less wall-clock at n=500, 1000 (see response to Reviwer VGWK). Against LKH-3: 21.4% aggregate CPU reduction at preserved quality.
-
Versus prior edge priors. Existing priors (-nearness, learned candidate sets, heatmaps) are instance-dependent: they score edges by likelihood of appearing in some good tour. RTDL is the first tour-dependent signal, scoring how badly an edge violates the cluster structure of the current solution. This enables plug-in use with any pretrained solver (six frameworks, no retraining), and sees edges static priors structurally cannot: -nearness provably protects the inter-cluster bridge needed for the optimum in Appendix U.1 (stock LKH: 9/15 seeds; RTDL-biased: 12/15). We also prove -nearness is a degenerate RTDL bar (Prop. 3.5) with , a strict generalization of LKH's 25-year-old candidate signal.
-
Versus RTD-Lite. RTD-Lite proves a pairing exists and intervals sum to an aggregate cost difference - but nothing about which edge receives which penalty. The edges bijection alone does not give a valid per-edge signal: Appendix X exhibits Gale's rank-matching, which satisfies the same sum yet penalizes MST edges that provably cannot contribute to suboptimality. Our new guarantees - the zero-penalty law stability under ties and perturbations, and the lower bound make the barcode an edge-wise penalty, and have no counterpart in RTD-Lite.
If the Reviewer believes a specific delta is smaller than claimed, we would be grateful to know which, and will address it with additional evidence. Otherwise, given the correctness issues are resolved and the contribution is demonstrated in matched comparisons against the strong previous results, we respectfully ask the Reviewer to consider raising the score.
Response to Reviewer sbb5
W1. On LKH improvement.
24.1% instead of 21.4% is a typo. We are fixing abstract/main text in the revision.
W2. On L2C gains and inexpensive region-selection baselines.
Prioritizing long tour edges performs similarly to uniform region selection (the difference is not statistically significant), whereas RTDL-guided selection improves the gap by 0.47–0.56 percentage points. We are adding new experimental results to the revision.
W3. On the p-value the Introduction.
You are correct about the p-value statement. The main text says p<10−3 for the L2C result, but Table 3 reports p=7.21×10−4 for n=500, p=2.8×10−2 for n=2000. We are replacing p<10−3 with p<0.05 in the Introduction, in the paper’s revision.
W4. On ATSP/HCP scope.
The current ATSP/HCP experiments are proof-of-concept via the Jonker-Volgenant symmetric reduction, as stated in Section 4.3, and they do show gains in solution quality, including HCP-200 exact solutions increasing from 1.0% to 7.0% and HCP-500 from 0.0% to 13.0%. We agree this does not establish a fundamentally new asymmetric or HCP-specific algorithm. We are narrowing the claim: the method applies to weighted graphs and can be used after standard reductions, but the paper's main empirical evidence is for symmetric TSP and TSP-based neural pipelines.
Concluding remarks. We hope these additional experiments address the Reviewer's concerns regarding L2C region-selection. We welcome any further questions and would appreciate reconsideration of the overall rating in light of the new evidence.