Research map / Learning theory and algorithms / Combinatorial and search optimization
Improved Approximation Algorithms for Clustered TSP and Subgroup Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Improves approximation ratios for the Subgroup Planning Problem (SGPP) and Clustered TSP (CTSP): a polynomial-time 2.167-approximation, an FPT 2.072-approximation parameterized by group size, and an FPT β-approximation parameterized by number of groups.
Problem
Clustered TSP (CTSP) and its generalization subgroup planning problem (SGPP) under a partial metric, where the tour must visit each vertex group consecutively; the goal is a minimum-weight tour with good approximation ratios.
Approach
Combines two polynomial-time algorithms (one using Hoogeveen's path TSP on the heaviest intra-group edge, one using a Christofides half-tour over contracted groups) with a trade-off analysis via an LP, and adds FPT variants using dynamic programming over group paths.
Key results
- Polynomial-time 2.167-approximation for SGPP (improving 3), via min of Alg.1 (1.5+2τ-2δ) and Alg.2 (1.5+0.5γ+0.5δ) bounds.
- FPT 2.072-approximation parameterized by group size in O*(2^t) time, improving 2.5.
- FPT β-approximation parameterized by number of groups in O*(2^m) time; with β=5/3 implementation, Alg.4 achieved the best tour weight on every tested small instance (e.g., xqf131 with m=4: 3603 vs 3855 for Alg.1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Improve the polynomial-time approximation algorithm for SGPP from ratio 3 to 2.167 | SGPP · SGPP | approximation ratio: 3 -> 2.167 | Helped |
| Improve the FPT approximation algorithm parameterized by group size t from ratio 2.5 to 2.072 | SGPP · SGPP, parameterized by group size t | approximation ratio: 2.5 -> 2.072 | Helped |
| Use the proposed FPT algorithm parameterized by number of groups m instead of the previous CTSP algorithm | SGPP and CTSP · CTSP, parameterized by number of groups m | approximation ratio: 1.667 -> β < 1.5 | Helped |
| Use Alg.4 instead of Alg.1 | SGPP · xqf131 (m=4) | tour weight: 3855 -> 3603 | Helped |
| Use Alg.4 instead of Alg.2 | SGPP · xqf131 (m=4) | tour weight: 4106 -> 3603 | Helped |
| Use Alg.1 instead of Alg.2 | SGPP · 35 VLSI instances with t=10 | tour weight | Mixed |
| Use Alg.3 instead of SYKK | SGPP · 35 VLSI instances with t=10 | tour weight | No clear effect |
Surprising findings
- Alg.2 (Christofides-based half-tour) performed worst in experiments despite being part of the best worst-case ratio, and was the slowest of the polynomial-time algorithms.
Limitations
- Alg.4 is exponential in the number of groups and runs over 3600s even for instances with only hundreds of vertices, limiting experiments to small instances.
- Experiments used a 5/3 PTSP approximation in place of the best beta, so the implemented ratio is 5/3 rather than the theoretical beta.
- Experiments use synthetic random groups and synthetic intra-group weights rather than real application data.
Experimental setup
Datasets: VLSI TSP instances
Benchmarks: VLSI TSP instances (102 instances; 35 used for the first experiment, subset for the second)
Metrics: tour weight running time (s)
Baselines: SYKK (Sumita et al. 2017) Alg.1 Alg.2 Alg.3
Builds on: Christofides algorithm Hoogeveen PTSP 5/3 approximation Bao and Liu CTSP 13/6 approximation Sumita et al. 2017 SGPP algorithms Anily-Bramel-Hertz OCTSP
Closest papers by meaning
- FPT Approximation Algorithms for TSP on Non-Metric Graphs (AAAI 2026 · similarity 0.85)
- Large-Scale Multi-Robot Coverage Path Planning via Local Search (AAAI 2024 · similarity 0.83)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.82)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.82)
- Heterogeneous Multi-Robot Graph Coverage with Proximity and Movement Constraints (AAAI 2025 · similarity 0.81)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.81)
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.