Better approximation algorithms for clustered TSP and subgroup planning

DOI10.1016/J.COR.2026.107471MaRDI QIDQ7255504zbMATH OpenFDO

Authors Jingyang Zhao, Mingyu Xiao, Junqiang Peng, Ziliang Xiong

Publication date 1 June 2026

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COR.2026.107471

zbMATH Keywords

approximation algorithmsclustered TSPcombinatorial optimizationFPT approximation algorithmssubgroup planning

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites work

• A (slightly) improved approximation algorithm for metric TSP
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• A 1.5-approximation for path TSP
• A Dynamic Programming Approach to Sequencing Problems
• A transformation technique for the clustered generalized traveling salesman problem with applications to logistics
• An Approximation Algorithm for the Traveling Salesman Problem with Backhauls
• An exact algorithm for the clustered travelling salesman problem
• An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
• An improved approximation algorithm for the clustered traveling salesman problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Approximation algorithms for not necessarily disjoint clustered TSP
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Efficient algorithms for finding maximum matching in graphs
• GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• Improving approximation ratios for the clustered traveling Salesman problem
• Improving Christofides' algorithm for the s-t path TSP
• Metaheuristics for the tabu clustered traveling salesman problem
• P-Complete Approximation Problems
• Procedures for travelling salesman problems with additional constraints
• Reducing Path TSP to TSP
• Restricted delivery problems on a network
• Some applications of the clustered travelling salesman problem
• Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs

This page was built for publication: Better approximation algorithms for clustered TSP and subgroup planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7255504)