IMPROVING APPROXIMATION RATIOS FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM
-
- Kawasaki Masamune
- Tokyo Institute of Technology
-
- Takazawa Kenjiro
- Hosei University
Search this article
Abstract
<p>The clustered traveling salesman problem (CTSP) is a generalization of the traveling salesman problem (TSP) in which the set of cities is divided into clusters and the salesman must consecutively visit the cities of each cluster. It is well known that TSP is NP-hard, and hence CTSP is NP-hard as well. Guttmann-Beck et al. (2000) designed approximation algorithms for several variants of CTSP by decomposing it into subproblems including the traveling salesman path problem (TSPP). In this paper, we improve approximation ratios by applying a recent improved approximation algorithm for TSPP by Zenklusen (2019).</p>
Journal
-
- Journal of the Operations Research Society of Japan
-
Journal of the Operations Research Society of Japan 63 (2), 60-70, 2020-04-30
The Operations Research Society of Japan
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390285300155340672
-
- NII Article ID
- 130007838841
-
- NII Book ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- NDL BIB ID
- 030384339
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- NDL
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed