A Fast Quasi-Linear Heuristic for the Close-Enough Traveling Salesman Problem
Pith reviewed 2026-05-15 01:11 UTC · model grok-4.3
The pith
A hierarchical clustering heuristic solves the close-enough traveling salesman problem in expected O(n log n) time while staying within 2% of best-known tours.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The algorithm adapts the pair-center clustering paradigm to circular neighborhoods: a hierarchical clustering phase merges nearby disks into proxy circles using an R*-tree for efficient spatial queries, and a construction phase incrementally expands the hierarchy into a feasible tour while maintaining and locally optimizing tour points. Lightweight local improvements, selective reinsertion and constrained point reoptimization, reduce local inefficiencies without compromising scalability. The algorithm runs in expected O(n log n) time and, on benchmark instances reconstructed from the Mennell dataset, produces solutions within roughly 0-2% of state-of-the-art best-known values while requiring
What carries the argument
Hierarchical clustering of disks into proxy circles using an R*-tree for spatial queries, combined with incremental tour construction and lightweight local improvements.
Load-bearing premise
The hierarchical clustering combined with lightweight local improvements will reliably avoid poor local optima and maintain solution quality close to best-known across diverse CETSP instances without needing instance-specific tuning.
What would settle it
Observing whether the solution gap exceeds 2% or runtime grows superlinear on new large benchmark instances not from the Mennell dataset.
read the original abstract
We introduce a fast, quasi-linear-time heuristic for the Close-Enough Traveling Salesman Problem (CETSP), a continuous generalization of the Euclidean TSP in which each target is a disk that must be intersected. The method adapts the pair-center clustering paradigm to circular neighborhoods: a hierarchical clustering phase merges nearby disks into proxy circles using an R*-tree for efficient spatial queries, and a construction phase incrementally expands the hierarchy into a feasible tour while maintaining and locally optimizing tour points. Lightweight local improvements, selective reinsertion and constrained point reoptimization, reduce local inefficiencies without compromising scalability. The algorithm runs in expected O(n log n) time and, on benchmark instances reconstructed from the Mennell dataset, produces solutions within roughly 0-2% of state-of-the-art best-known values while requiring orders-of-magnitude less runtime than population-based metaheuristics. The approach trades some final-solution optimality for dramatic gains in speed and scalability, making it suitable for very large CETSP instances.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces a fast quasi-linear heuristic for the Close-Enough Traveling Salesman Problem (CETSP) that adapts pair-center clustering to circular neighborhoods via R*-tree hierarchical merging of disks, followed by an incremental construction phase with selective reinsertion and constrained local point reoptimization. It claims an expected O(n log n) runtime and, on Mennell-reconstructed benchmark instances, produces tours within roughly 0-2% of best-known values while running orders of magnitude faster than population-based metaheuristics.
Significance. If the runtime bound and empirical quality claims hold, the work supplies a practical, scalable heuristic for large CETSP instances where exact solvers or heavy metaheuristics become prohibitive. The explicit speed-quality tradeoff and use of standard R*-tree primitives make the method immediately usable in applications requiring rapid approximate tours over many disk neighborhoods.
major comments (1)
- [Experimental results] Experimental results section: the 0-2% gap to best-known values is presented without full instance definitions, number of independent runs, or error bars, leaving the quality claim only moderately supported despite the supplied runtime profiles and pseudocode.
Simulated Author's Rebuttal
We thank the referee for the supportive summary, significance assessment, and recommendation of minor revision. We address the single major comment below and will incorporate the requested clarifications into the revised manuscript.
read point-by-point responses
-
Referee: [Experimental results] Experimental results section: the 0-2% gap to best-known values is presented without full instance definitions, number of independent runs, or error bars, leaving the quality claim only moderately supported despite the supplied runtime profiles and pseudocode.
Authors: We agree that the experimental reporting can be strengthened for clarity. In the revised manuscript we will add an appendix or expanded table that lists the complete parameters of all Mennell-reconstructed benchmark instances (radii, coordinates, and n values), explicitly state that the heuristic is deterministic and therefore reports results from a single run per instance, and include error bars or standard-deviation notes for any stochastic baselines we compare against. These additions will make the 0–2 % quality claim fully reproducible and better supported while preserving the existing runtime profiles and pseudocode. revision: yes
Circularity Check
No significant circularity detected
full rationale
The manuscript describes a constructive heuristic that combines R*-tree hierarchical clustering of disks, incremental tour construction, and bounded local search steps. The O(n log n) runtime bound follows directly from standard R*-tree query complexity under the stated disk-distribution assumption, while solution quality is reported as an empirical speed-quality tradeoff against externally known best values on Mennell-reconstructed instances. No equations reduce performance claims to fitted parameters, no self-citations serve as load-bearing uniqueness theorems, and no ansatz or renaming of known results is invoked to justify the central claims. The derivation chain therefore remains self-contained against external benchmarks.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.