Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (17): 15-17.

Previous Articles     Next Articles

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.

Key words: set cover, approximation algorithm, 0-1 program, dual program, Linear Interactive and General Optimizer(LINGO)

摘要: 集合覆盖问题在网络设计领域中有着良好的应用背景,但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型,给出了源于贪心思想的近似算法,并从原始-对偶规划的角度进行了证明,基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。

关键词: 集合覆盖, 近似算法, 0-1规划, 对偶规划, 线性交互式通用优化器(LINGO)