文献类型：期刊文章

作　　者：崔鹏[1] 刘红静[2]

机构地区：[1]中国人民大学信息资源管理学院,北京100872 [2]保定市财贸学校,河北保定071000

出　　处：《软件学报》

年　　份：2006

卷　　号：17

期　　号：7

起止页码：1494-1500

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI(收录号：20063410082584)、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

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

关 键 词：测试集问题  集合覆盖贪心算法  去随机方法  冗余测试集问题  

分 类 号：TP301]