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

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (17): 15-17.

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

王继强

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

出版日期:2013-09-01 发布日期:2013-09-13

Model and algorithm for set cover problem

WANG Jiqiang

School of Mathematics and Quantitative Economics, Shandong University of Finance and Economics, Jinan 250014, China

Online:2013-09-01 Published:2013-09-13

摘要/Abstract

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

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

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）

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

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

[1]	斯燕方，殷志祥，崔建中，杨静，唐震. 简单0-1规划问题的动态DNA折纸计算模型[J]. 计算机工程与应用, 2020, 56(4): 168-174.
[2]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[3]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[4]	聂文艳1，王仲根2. 应用ACA算法快速分析导体目标电磁散射特性[J]. 计算机工程与应用, 2015, 51(4): 232-234.
[5]	肖华勇，马丽娜，程海礁. 老板数独的方程求解算法研究[J]. 计算机工程与应用, 2014, 50(9): 41-44.
[6]	纪鹏宇1，谢红1，赵蕴龙2. 一种中继节点上的网络-信道编码联合设计方案[J]. 计算机工程与应用, 2012, 48(34): 102-106.
[7]	陈露晨. 基于0-1规划的快速图像阈值分割算法[J]. 计算机工程与应用, 2012, 48(10): 197-199.
[8]	王继强. 基于TSP的图的路包装问题的算法研究[J]. 计算机工程与应用, 2011, 47(21): 220-222.
[9]	何晓琼，陈冲，李荣珩. 工厂地址集中的k-种产品选址问题的近似算法[J]. 计算机工程与应用, 2010, 46(8): 238-241.
[10]	高文宇. 有向图连通支配集求解算法[J]. 计算机工程与应用, 2010, 46(21): 9-13.
[11]	杨昆¹，徐静²，张彦斌¹. 基因选择的0-1规划模型和算法[J]. 计算机工程与应用, 2010, 46(20): 184-187.
[12]	黄金贵. 具有优先链约束的网格作业多资源调度问题[J]. 计算机工程与应用, 2009, 45(6): 48-51.
[13]	王进科,王华. 遗传算法在聚合组播问题优化中的应用[J]. 计算机工程与应用, 2009, 45(5): 82-85.
[14]	黄金贵. 应用团划分方法改进多处理机任务近似调度[J]. 计算机工程与应用, 2009, 45(4): 4-8.
[15]	许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.