arXiv preprint ·
The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours. Each selected tour must not exceed a prescribed multiple of the optimal tour length, while the maximum pairwise Jaccard similarity within the selected set is minimized. This formulation is important for applications requiring both solution quality and fault tolerance, such as logistics planning, robotics, and strategic patrolling. We propose a novel hybrid framework that decomposes D-TSP into a sampling stage and a selection stage. The selection stage is a max-min dispersion problem, for which any approximation better than a factor of two is NP-hard; we therefore focus on the sampling stage. Our contributions are both theoretical and empirical. Theoretically, we give two end-to-end guarantees for the optimal sampling distribution, from two perspectives: including an optimal set in the sampled pool, or having at least $k$ mutually distant tours in the pool. The second reduces the number of samples from exponential to linear in $k$, at the cost of weakening the benchmark from the best $k$ tours to the best $βk$ for some $β> 1$. For practical use, we prove that a pipeline that samples spanning trees and then converts to tours does not hurt the quality of the pool in principle. Empirically, both objectives are learnable, and our experiments not only validate the analysis but also outperform the baselines on both in-distribution and out-of-distribution instances, by a single trained model with no fine-tuning.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
CyberHull: Deterministic Malicious URL Isolation via Convex Hull
How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
Splitting Planar Necklaces with Few Straight Cuts
Coresets for $k$-Means: When Does Uniform Sampling Suffice?
A Bochner Weitzenböck Decomposition for Cellular Sheaf Laplacians, Curvature and Neural Sheaf Diffusion
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.