Summary
|
For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE. |
|
Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem Kazuro KIMURA Shinya HIGA Masao OKITA Fumihiko INO Publication IEICE TRANSACTIONS on Information and Systems Vol.E102-D No.12 pp.2329-2340 Publication Date: 2019/12/01 Publicized: 2019/08/23 Online ISSN: 1745-1361 DOI: 10.1587/transinf.2019PAP0008 Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking) Category: Fundamentals of Information System Keyword: symmetric traveling salesman problem, Held-Karp algorithm, parallelization, meet in the middle, GPU, Full Text: PDF(597KB)>>
Summary: In this paper, we propose an acceleration method for the Held-Karp algorithm that solves the symmetric traveling salesman problem by dynamic programming. The proposed method achieves acceleration with two techniques. First, we locate data-independent subproblems so that the subproblems can be solved in parallel. Second, we reduce the number of subproblems by a meet in the middle (MITM) technique, which computes the optimal path from both clockwise and counterclockwise directions. We show theoretical analysis on the impact of MITM in terms of the time and space complexities. In experiments, we compared the proposed method with a previous method running on a single-core CPU. Experimental results show that the proposed method on an 8-core CPU was 9.5-10.5 times faster than the previous method on a single-core CPU. Moreover, the proposed method on a graphics processing unit (GPU) was 30-40 times faster than that on an 8-core CPU. As a side effect, the proposed method reduced the memory usage by 48%. | ||||||||||
| ||||||||||