| Presentation | 2009-05-14 Proposal and Implementation of High Throughput Algorithm for Combination Generation Akira TSUJI, Norio YAMAGAKI, Satoshi KAMIYA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Combinatorial optimization problems are widely exist. Generally they are solved by approximate means like greedy method because they are categorized as NP-hard. However, in several cases, the solution is likely to be local optimized. In the worst case, no solutions can be obtained. Meanwhile, even if brute force method like enumeration method is used, there is a possibility that optimized solutions can be obtained within realistic time because of resent performance improvement of processors and other reasons. For speeding up the enumeration method, a method of fast combination generation is required. In this paper, we clarify the problems for speeding up of enumeration method through performance evaluations of existing combination generation algorithms. Moreover, we propose a faster combination generation algorithm than existings. In the results of the performance evaluations, the dedicated hardware of the proposed algorithm achieves about 500 times faster than software of the existing algorithm and about 10 times than the dedicated hardware of that. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | combinatorial optimization problem / enumeration method / combination generation / FPGA |
| Paper # | RECONF2009-5 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2009/5/7(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Reconfigurable Systems (RECONF) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Proposal and Implementation of High Throughput Algorithm for Combination Generation |
| Sub Title (in English) | |
| Keyword(1) | combinatorial optimization problem |
| Keyword(2) | enumeration method |
| Keyword(3) | combination generation |
| Keyword(4) | FPGA |
| 1st Author's Name | Akira TSUJI |
| 1st Author's Affiliation | System IP Core Research Laboratories, NEC Corporation() |
| 2nd Author's Name | Norio YAMAGAKI |
| 2nd Author's Affiliation | System IP Core Research Laboratories, NEC Corporation |
| 3rd Author's Name | Satoshi KAMIYA |
| 3rd Author's Affiliation | System IP Core Research Laboratories, NEC Corporation |
| Date | 2009-05-14 |
| Paper # | RECONF2009-5 |
| Volume (vol) | vol.109 |
| Number (no) | 26 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |