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

• 作者: 王继强
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 集合覆盖 近似算法 0-1规划 对偶规划 线性交互式通用优化器(LINGO)
• 年，卷（期）: 2013,（17）
• 页码范围: 15-17,72
• 页数: 4页
• 分类号: Q784|TP301.6
• 字数: 3273字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1303-0383

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王继强	山东财经大学数学与数量经济学院	9	48	3.0	6.0