Research map / Graph learning / Graph algorithms and clustering
GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets
Jingtao Tang, Hang Ma
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GHOST with lower-bound graph (LBG) instead of MICP | GCS-TSP solver · Point-GCS (complete GCS, N in [5, 25]) | feasibility / runtime: MICP fails to produce feasible solutions for N > 13 | Improved |
| use GHOST instead of MICP | GCS-TSP solver · Linear-GCS (incomplete, M in [10, 50] edges) | feasibility / runtime: MICP fails for M > 19 | Improved |
| use GHOST instead of MICP | GCS-TSP solver · Bezier-GCS | feasibility: MICP fails on any Bezier-GCS instance | Improved |
| replace LBG-based costs with Chebyshev-center edge-cost graph (ECG) (ablation) | GHOST · Point, Linear and Bezier GCS-TSP | trajectory cost and runtime | Hurt |
| replace systematic best-first tour search with greedy depth-first search (ablation) | GHOST · Point, Linear and Bezier GCS-TSP | trajectory cost and runtime | Hurt |
| use bounded-suboptimal 0.5-GHOST instead of optimal GHOST (ablation) | GHOST · Point, Linear and Bezier GCS-TSP | solution quality and runtime | Mixed |
| extend triplet LBG and RTSP ILP to 4-tuples (ablation) | GHOST · GCS-TSP | bound tightness vs overhead | No clear effect |
| compare paths from different tours in parallel (ablation) | GHOST · GCS-TSP | efficiency | No clear effect |
Closest papers by meaning
- Neural Combinatorial Optimization for Time Dependent Traveling Salesman Problem (NeurIPS 2025 · similarity 0.86)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.86)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.84)
- Destroy and Repair Using Hyper-Graphs for Routing (AAAI 2025 · similarity 0.84)
- Improved Approximation Algorithms for Clustered TSP and Subgroup Planning (AAAI 2025 · similarity 0.83)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
