Model and algorithm for set cover problem

Abstract

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）

WANG Jiqiang. Model and algorithm for set cover problem[J]. Computer Engineering and Applications, 2013, 49(17): 15-17.

王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.

[1]	SI Yanfang, YIN Zhixiang, CUI Jianzhong, YANG Jing, TANG Zhen. Dynamic DNA Origami Computing Model for Simple 0-1 Programming Problem [J]. Computer Engineering and Applications, 2020, 56(4): 168-174.
[2]	ZENG Weixin1, ZHAO Xiang1，2, FENG Tao1, TANG Jiuyang1，2. Improved domain-oriented named entity disambiguation method study [J]. Computer Engineering and Applications, 2018, 54(17): 126-134.
[3]	JIANG Xiaojuan1, ZHANG An1, CHEN Yong1, CHEN Guangting2. Algorithm for minimum internal nodes constrained spanning tree problem [J]. Computer Engineering and Applications, 2017, 53(10): 35-37.
[4]	YU Fuping1，2, SHEN Di1. Improved smoothed [l0] approximation algorithm based on Quasi-Newton direction [J]. Computer Engineering and Applications, 2013, 49(22): 215-218.
[5]	ZANG Wenke1, XIA Ruifang2, LIU Xiyu1. DNA solution on surface for minimal set covering problem [J]. Computer Engineering and Applications, 2012, 48(22): 14-17.
[6]	CHEN Luchen. Fast thresholding for image segmentation based on 0-1 programming [J]. Computer Engineering and Applications, 2012, 48(10): 197-199.
[7]	WANG Jiqiang. Research of algorithm for path packing problem in graphs based on TSP [J]. Computer Engineering and Applications, 2011, 47(21): 220-222.
[8]	HE Xiao-qiong，CHEN Chong，LI Rong-heng. Approximation algorithms for k-product centralized facility location problem [J]. Computer Engineering and Applications, 2010, 46(8): 238-241.
[9]	YANG Kun¹，XU Jing²，ZHANG Yan-bin¹. 0-1 programming model and algorithm for gene selection [J]. Computer Engineering and Applications, 2010, 46(20): 184-187.
[10]	HUANG Jin-gui. Multi-resource scheduling of grid job with precedence chain constraints [J]. Computer Engineering and Applications, 2009, 45(6): 48-51.
[11]	WANG Jin-ke,WANG Hua. Application of genetic algorithm in aggregated multicast optimization [J]. Computer Engineering and Applications, 2009, 45(5): 82-85.
[12]	HUANG Jin-gui. Clique partition based approximation scheduling algorithm on multiprocessor tasks [J]. Computer Engineering and Applications, 2009, 45(4): 4-8.
[13]	QUAN Jun-lin,LU Lu. Research test case suite minimization based on genetic algorithm [J]. Computer Engineering and Applications, 2009, 45(19): 58-61.
[14]	YI Bin¹,Li Rong-heng². Several progress about approximation algorithm for k-PUFLPN [J]. Computer Engineering and Applications, 2009, 45(17): 221-224.
[15]	WU Yan,ZHANG Chun-hui. Application of minimum consistent subset cover in incomplete rule set [J]. Computer Engineering and Applications, 2009, 45(1): 147-148.

Model and algorithm for set cover problem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics