| Presentation | 2005-01-28 Performance Evaluation of PC Cluster-based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem Yoshitaka SHIMODA, Satoshi TAOKA, Daisuke TAKAFUJI, Toshimasa WATANABE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, we propose some sending-node selection strategies and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Parallel branch-and-bound algorithms / Combinatorial optimization problems / MPI / Optimum solutions |
| Paper # | COMP2004-68 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/1/21(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 | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Performance Evaluation of PC Cluster-based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem |
| Sub Title (in English) | |
| Keyword(1) | Parallel branch-and-bound algorithms |
| Keyword(2) | Combinatorial optimization problems |
| Keyword(3) | MPI |
| Keyword(4) | Optimum solutions |
| 1st Author's Name | Yoshitaka SHIMODA |
| 1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
| 2nd Author's Name | Satoshi TAOKA |
| 2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| 3rd Author's Name | Daisuke TAKAFUJI |
| 3rd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| 4th Author's Name | Toshimasa WATANABE |
| 4th Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| Date | 2005-01-28 |
| Paper # | COMP2004-68 |
| Volume (vol) | vol.104 |
| Number (no) | 642 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |