| Presentation | 2018-12-21 Accelerating the Held-Karp Algorithm for the symmetric traveling salesman problem Kazuro Kimura, Shinya Higa, Masao Okita, Fumihiko Ino, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(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) |
| Keyword(in English) | symmetric traveling salesman problem / Held-Karp algorithm / parallelization / meet in the middle / GPU |
| Paper # | CAS2018-84,ICD2018-68,CPSY2018-50 |
| Date of Issue | 2018-12-14 (CAS, ICD, CPSY) |
| Conference Information | |
| Committee | ICD / CPSY / CAS |
|---|---|
| Conference Date | 2018/12/21(3days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hideto Hidaka(Renesas) / Koji Nakano(Hiroshima Univ.) / Hideaki Okazaki(Shonan Inst. of Tech.) |
| Vice Chair | Makoto Nagata(Kobe Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Taizo Yamawaki(Hitachi) |
| Secretary | Makoto Nagata(Panasonic) / Hidetsugu Irie(Tohoku Univ.) / Takashi Miyoshi(Utsunomiya Univ.) / Taizo Yamawaki(Hokkaido Univ.) |
| Assistant | Hiroyuki Ito(Tokyo Inst. of Tech.) / Masatoshi Tsuge(Socionext) / Tetsuya Hirose(Kobe Univ.) / Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Motoi Yamaguchi(Renesas Electronics) |
| Paper Information | |
| Registration To | Technical Committee on Integrated Circuits and Devices / Technical Committee on Computer Systems / Technical Committee on Circuits and Systems |
|---|---|
| Language | JPN |
| 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 |
| 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.) |
| Date | 2018-12-21 |
| Paper # | CAS2018-84,ICD2018-68,CPSY2018-50 |
| Volume (vol) | vol.118 |
| Number (no) | CAS-373,ICD-374,CPSY-375 |
| Page | pp.pp.31-36(CAS), pp.31-36(ICD), pp.31-36(CPSY), |
| #Pages | 6 |
| Date of Issue | 2018-12-14 (CAS, ICD, CPSY) |