Paper Abstract and Keywords |
Presentation |
2018-12-21 16:00
Accelerating the Held-Karp Algorithm for the symmetric traveling salesman problem Kazuro Kimura, Shinya Higa, Masao Okita, Fumihiko Ino (Osaka Univ.) CAS2018-84 ICD2018-68 CPSY2018-50 Link to ES Tech. Rep. Archives: ICD2018-68 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
In this paper, we propose an acceleration method for the Held-Karp algorithm that solves the symmetric traveling salesman problem. 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 to be solved by separating the optimal path into two parts. In experiments, we compared an existing method running on a single-core CPU with the proposed method running on a multi-core CPU. Experimental results show that the proposed method on a multi-core CPU was 9.5-10.5 times faster than the existing method on a single-core CPU. Moreover, the proposed method on a graphics processing unit (GPU) was 300-400 times faster than the existing method on a single-core CPU. As a side effect, the proposed method reduced the memory usage by 48 %. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
symmetric traveling salesman problem / Held-Karp algorithm / parallelization / meet in the middle / GPU / / / |
Reference Info. |
IEICE Tech. Rep., vol. 118, no. 375, CPSY2018-50, pp. 31-36, Dec. 2018. |
Paper # |
CPSY2018-50 |
Date of Issue |
2018-12-14 (CAS, ICD, CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
CAS2018-84 ICD2018-68 CPSY2018-50 Link to ES Tech. Rep. Archives: ICD2018-68 |
Conference Information |
Committee |
ICD CPSY CAS |
Conference Date |
2018-12-21 - 2018-12-23 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
|
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
CPSY |
Conference Code |
2018-12-ICD-CPSY-CAS |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Accelerating the Held-Karp Algorithm for the symmetric traveling salesman problem |
Sub Title (in English) |
|
Keyword(1) |
symmetric traveling salesman problem |
Keyword(2) |
Held-Karp algorithm |
Keyword(3) |
parallelization |
Keyword(4) |
meet in the middle |
Keyword(5) |
GPU |
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Kazuro Kimura |
1st Author's Affiliation |
Osaka University (Osaka Univ.) |
2nd Author's Name |
Shinya Higa |
2nd Author's Affiliation |
Osaka University (Osaka Univ.) |
3rd Author's Name |
Masao Okita |
3rd Author's Affiliation |
Osaka University (Osaka Univ.) |
4th Author's Name |
Fumihiko Ino |
4th Author's Affiliation |
Osaka University (Osaka Univ.) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2018-12-21 16:00:00 |
Presentation Time |
20 minutes |
Registration for |
CPSY |
Paper # |
CAS2018-84, ICD2018-68, CPSY2018-50 |
Volume (vol) |
vol.118 |
Number (no) |
no.373(CAS), no.374(ICD), no.375(CPSY) |
Page |
pp.31-36 |
#Pages |
6 |
Date of Issue |
2018-12-14 (CAS, ICD, CPSY) |
|