PARALLEL AND SERIAL HEURISTICS FOR THE MINIMUM SET COVER PROBLEM

作     者：CHAKRAVARTY, S SHEKHAWAT, A 

作者机构：1. Department of Computer Science SUNY at Buffalo 14260 Buffalo NY USA 

出 版 物：《JOURNAL OF SUPERCOMPUTING》 (超高速计算杂志)

年 卷 期：1992年第5卷第4期

页      面：331-345页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：PARALLEL HEURISTIC ALGORITHMS APPROXIMATION ALGORITHMS OPTIMIZATION PROBLEMS MINIMUM SET COVER PROBLEM 

摘      要：We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.