Improved Approximation Algorithms for Clustered TSP and Subgroup Planning

Abstract

In the Clustered TSP (CTSP), we are given an edge-weighted graph satisfying the triangle inequality property, and a family of pairwise disjoint vertex groups. The goal is to find a minimum weight tour that includes all vertices, ensuring that the vertices within each group appear consecutively on the tour. The subgroup planning problem (SGPP) is an extension of CTSP by relaxing some triangle inequality requirements on edge weights. CTSP and SGPP have plentiful applications in AI and robotics. In this paper, we design three improved approximation algorithms for SGPP and CTSP. First, we propose a polynomial-time 2.167-approximation algorithm for SGPP, improving the previous ratio of 3 (IJCAI 2017). Second, we give an FPT 2.072-approximation algorithm for SGPP parameterized by the maximum group size, improving the previous ratio of 2.5 (IJCAI 2017). Third, we prove an FPT (β<1.5)-approximation algorithm for SGPP parameterized by the number of groups, which even improves the previous ratio 1.667 for CTSP (ORL 1999). We also conduct experiments to evaluate the performance of our algorithms.