| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2009-05-14 15:10 Proposal and Implementation of High Throughput Algorithm for Combination Generation Akira Tsuji, Norio Yamagaki, Satoshi Kamiya (NEC)  RECONF2009-5 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (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) |
| (in English) | combinatorial optimization problem / enumeration method / combination generation / FPGA / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 109, no. 26, RECONF2009-5, pp. 25-30, May 2009. | |
| Paper # | RECONF2009-5 | |
| Date of Issue | 2009-05-07 (RECONF) | |
| 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 | RECONF2009-5 |
|
| Conference Information | |
| Committee | RECONF |
| Conference Date | 2009-05-14 - 2009-05-15 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | RECONF |
| Conference Code | 2009-05-RECONF |
| Language | Japanese |
| 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 |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Akira Tsuji |
| 1st Author's Affiliation | NEC Corporation (NEC) |
| 2nd Author's Name | Norio Yamagaki |
| 2nd Author's Affiliation | NEC Corporation (NEC) |
| 3rd Author's Name | Satoshi Kamiya |
| 3rd Author's Affiliation | NEC Corporation (NEC) |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 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 | () |
| Speaker | Author-1 |
| Date Time | 2009-05-14 15:10:00 |
| Presentation Time | 30 minutes |
| Registration for | RECONF |
| Paper # | RECONF2009-5 |
| Volume (vol) | vol.109 |
| Number (no) | no.26 |
| Page | pp.25-30 |
| #Pages | 6 |
| Date of Issue | 2009-05-07 (RECONF) |
[Return to Top Page]