Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem

Kazuro KIMURA  Shinya HIGA  Masao OKITA  Fumihiko INO  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.12   pp.2329-2340
Publication Date: 2019/12/01
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
symmetric traveling salesman problem,  Held-Karp algorithm,  parallelization,  meet in the middle,  GPU,  

Full Text: PDF(597KB)>>
Buy this Article

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%.