An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization

This paper focuses on a generalization of the traveling salesman problem (TSP), called the subpath planning problem (SPP). Given 2n vertices and n independent edges on a metric space, we aim to find a shortest tour that contains all the edges. SPP is one of the fundamental problems in both artificial intelligence and robotics. Our main result is to design a 1. 5-approximation algorithm that runs in polynomial time, improving the currently best approximation algorithm. The idea is direct use of techniques developed for TSP. In addition, we propose a generalization of SPP called the subgroup planning problem (SGPP). In this problem, we are given a set of disjoint groups of vertices, and we aim to find a shortest tour such that all the vertices in each group are traversed sequentially. We propose a 3-approximation algorithm for SGPP. We also conduct numerical experiments. Compared with previous algorithms, our algorithms improve the solution quality by more than 10% for large instances with more than 10, 000 vertices.

Authors

• Hanna Sumita Tokyo Institute of Technology
• Yuma Yonebayashi
• Naonori Kakimura Department of Mathematics, Keio University
• Ken-ichi Kawarabayashi National Institute of Informatics The University of Tokyo

Keywords

• Combinatorial & Heuristic Search: Combinatorial search/optimisation
• Planning and Scheduling: Theoretical Foundations of Planning