TY - GEN
T1 - An improved approximation algorithm for the subpath planning problem and its generalization
AU - Sumita, Hanna
AU - Yonebayashi, Yuma
AU - Kakimura, Naonori
AU - Kawarabayashi, Ken Ichi
N1 - Funding Information:
The authors would like to thank the anonymous reviewers for their valuable comments, particularly for pointing out the connection to CTSP. This work is supported by JST ERATO Grant Number JPMJER1201, Japan.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85031939112&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031939112&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2017/616
DO - 10.24963/ijcai.2017/616
M3 - Conference contribution
AN - SCOPUS:85031939112
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 4412
EP - 4418
BT - 26th International Joint Conference on Artificial Intelligence, IJCAI 2017
A2 - Sierra, Carles
PB - International Joint Conferences on Artificial Intelligence
T2 - 26th International Joint Conference on Artificial Intelligence, IJCAI 2017
Y2 - 19 August 2017 through 25 August 2017
ER -