### Model and algorithm for set cover problem

WANG Jiqiang

1. School of Mathematics and Quantitative Economics, Shandong University of Finance and Economics, Jinan 250014, China
• Online:2013-09-01 Published:2013-09-13

### 集合覆盖问题的模型与算法

1. 山东财经大学 数学与数量经济学院，济南 250014

Abstract: The set cover problem has favourable applications in areas of network design, but it is NP-hard in computational complexity. A 0-1 program model is formulated for the set cover problem. An approximation algorithm deriving from greedy idea is put forward, and is proved from the angle of primal-dual program. A case study of sensor network optimal design based on LINGO software demonstrates correctness of the model and effectiveness of the algorithm.