Title :
On the parallel solution of set covering and set partitioning problems
Author :
Sen, Arunabha ; Goldberg, Loretta
Author_Institution :
Dept. of Comput. Sci. & Eng., Arizona State Univ., Tempe, AZ, USA
Abstract :
The development, implementation, and evaluation of parallel algorithms for solving set covering and set partitioning problems are described. Existing algorithms for these NP-complete problems cannot always determine an optimal solution for a problem instance in a reasonable amount of time. While the use of parallel processing is not expected to alleviate the suspected intractability of these problems, it is hoped that it will be possible to obtain optimal solutions to many more real world problems as the result of parallel processing. The computational results that were obtained using a 32-node Intel iPSC/2 hypercube system are described
Keywords :
computational complexity; hypercube networks; mathematics computing; parallel algorithms; set theory; 32-node Intel iPSC/2 hypercube; NP-complete problems; parallel algorithms; real world problems; set covering; set partitioning; Algorithm design and analysis; Computer science; Cost function; Hypercubes; Information retrieval; Integer linear programming; NP-complete problem; Parallel algorithms; Parallel processing; Partitioning algorithms;
Conference_Titel :
Signals, Systems and Computers, 1992. 1992 Conference Record of The Twenty-Sixth Asilomar Conference on
Conference_Location :
Pacific Grove, CA
Print_ISBN :
0-8186-3160-0
DOI :
10.1109/ACSSC.1992.269088
