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

Deep Approximation of Set Cover Greedy Algorithm for Test Set

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

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

出　　处：《软件学报》2006年第7期1494-1500,共7页Journal of Software

摘　　要：测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比2lnn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.5lnn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n1的加权冗余测试集问题的近似比的紧密下界(2o(1))lnn(1).Test set problem is a NP-hard problem with wide applications. Set cover greedy algorithm is one of the commonly used algorithms for the test set problem. It is an open problem if the approximation ratio 2ln n＋l directly derived from the set cover problem can be improved. The generalization of set cover greedy algorithm is used to solve the redundant test set problem arising in bioinformatics. This paper analyzes the distribution of the times for which the item pairs are differentiated, and proves that the approximation ratio of the set cover greedy algorithm for test set can be 1.5lnn＋0.5lnlnn＋2 by derandomization method, thus shrinks the gap in the analysis of the approximation ratio of this algorithm. In addit ion, this paper shows the tight lower bound （2-o（1））lnn-Θ（1） of the approximation ratio of set cover greedy algorithm for the weighted redundant test set with redundancy n-1.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]