测试集问题的集合覆盖贪心算法的深入近似

• 作者: 刘红静 崔鹏
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 测试集问题 集合覆盖贪心算法 去随机方法 冗余测试集问题
• 年，卷（期）: 2006,（7）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1494-1500
• 页数: 7页
• 分类号: TP301
• 字数: 5599字
• 语种: 中文

摘要

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔鹏	中国人民大学信息资源管理学院	9	18	2.0	4.0
2	刘红静		1	12	1.0	1.0