|
|||||
|
|
Solving the set cover problem on a supercomputer |
|
| Authors: | S J Shyu R C T Lee |
| Affiliation: | Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China a National Tsing Hua University, Hsinchu, Taiwan, Republic of China b Academia Sinica, Taipei, Taiwan, Republic of China |
| Abstract: | Supercomputers, such as CRAY-1, CRAY X-MP, CYBER 205, ETA10, … etc, have been regularly used for solving numerical problems. It is very rare that supercomputers are used to solve combinatorial problems. In this paper, we present an efficient vectorized algorithm to solve the set cover problem, which was proved to be NP-complete, on a supercomputer, ETA10-Q108. This algorithm fully utilizes vector instructions. Experiments are performed both on ETA10-Q108 and VAX/8550 for comparison. It takes VAX/8550 1174.5 seconds to solve a set of problem instances while it takes ETA10-Q108 only 26.6 seconds to solve the same set of problems. For a problem instance involving 7000 elements in a set, it takes 47.74 seconds for the supercomputer to solve it. If VAX/8550 is used, it will need roughly 15 hours. Thus we conclude that it is quite feasible to solve the set cover problem by using supercomputers. |
| Keywords: | Supercomputer vectorization set cover problem |
| 本文献已被 ScienceDirect 等数据库收录！ | |