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

作者：崔鹏; 刘红静

来源：软件学报, 2006, (07): 1494-1500.

• 测试集问题
• 集合覆盖贪心算法
• 去随机方法
• 冗余测试集问题 test set
• set cover greedy algorithm
• derandomization method
• redundant test set

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

• 单位
  中国人民大学; 华北电力大学（保定）