| Presentation | 1995/4/28 Parallel Branch-and-Bound Algorithms and Their Application to Parallel Computers Takahiro Miyamoto, Kazuhiko Iwasaki, Ken'ichi Hagihara, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Branch-and-bound algorithm is known to be an effective method to slove NP-hard combinational optimization problems such as knapsack problems. We propose parallel branch-and-bound algorithms for knapsack problems and work out some ideas. Those algorithms are applied to MIMD-type parallel computers (iPSC/860, KSR1). The average ratios of 100 example problems are 7.25 on iPSC/860(8PEs), 2.04 on KSR1(2PEs), and 15.48 on KSR1(32PEs) respectively. Proposed argorithms are shown to be effective. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | knapsack problems / branch-and-bound / iPSC/860 / KSR1 |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | CPSY |
|---|---|
| Conference Date | 1995/4/28(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 | Computer Systems (CPSY) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Parallel Branch-and-Bound Algorithms and Their Application to Parallel Computers |
| Sub Title (in English) | |
| Keyword(1) | knapsack problems |
| Keyword(2) | branch-and-bound |
| Keyword(3) | iPSC/860 |
| Keyword(4) | KSR1 |
| 1st Author's Name | Takahiro Miyamoto |
| 1st Author's Affiliation | Chiba University, Faculty of Engineering() |
| 2nd Author's Name | Kazuhiko Iwasaki |
| 2nd Author's Affiliation | Osaka University, Faculty of Scientific Engineering |
| 3rd Author's Name | Ken'ichi Hagihara |
| 3rd Author's Affiliation | Osaka University, Faculty of Scientific Engineering |
| Date | 1995/4/28 |
| Paper # | |
| Volume (vol) | vol.95 |
| Number (no) | 21 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |