The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서는 동적 프로그래밍을 통해 대칭형 여행 세일즈맨 문제를 해결하는 Held-Karp 알고리즘의 가속 방법을 제안한다. 제안된 방법은 두 가지 기법으로 가속을 달성한다. 먼저, 하위 문제를 병렬로 해결할 수 있도록 데이터 독립적인 하위 문제를 찾습니다. 둘째, 시계 방향과 시계 반대 방향 모두에서 최적의 경로를 계산하는 MITM(Meet in the Middle) 기술을 사용하여 하위 문제의 수를 줄입니다. 우리는 시간과 공간의 복잡성 측면에서 MITM의 영향에 대한 이론적 분석을 보여줍니다. 실험에서는 제안한 방법을 단일 코어 CPU에서 실행되는 이전 방법과 비교했습니다. 실험 결과, 8코어 CPU에서 제안한 방법이 싱글 코어 CPU에서 제안한 방법보다 9.5~10.5배 빠른 것으로 나타났다. 또한 제안된 방법은 그래픽 처리 장치(GPU)에서 30코어 CPU보다 40~8배 더 빠르다. 부작용으로 제안한 방법은 메모리 사용량을 48% 감소시켰다.
Kazuro KIMURA
Osaka University
Shinya HIGA
Osaka University
Masao OKITA
Osaka University
Fumihiko INO
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Kazuro KIMURA, Shinya HIGA, Masao OKITA, Fumihiko INO, "Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 12, pp. 2329-2340, December 2019, doi: 10.1587/transinf.2019PAP0008.
Abstract: 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%.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019PAP0008/_p
부
@ARTICLE{e102-d_12_2329,
author={Kazuro KIMURA, Shinya HIGA, Masao OKITA, Fumihiko INO, },
journal={IEICE TRANSACTIONS on Information},
title={Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem},
year={2019},
volume={E102-D},
number={12},
pages={2329-2340},
abstract={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%.},
keywords={},
doi={10.1587/transinf.2019PAP0008},
ISSN={1745-1361},
month={December},}
부
TY - JOUR
TI - Accelerating the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem
T2 - IEICE TRANSACTIONS on Information
SP - 2329
EP - 2340
AU - Kazuro KIMURA
AU - Shinya HIGA
AU - Masao OKITA
AU - Fumihiko INO
PY - 2019
DO - 10.1587/transinf.2019PAP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2019
AB - 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%.
ER -