Deep Approximation of Set Cover Greedy Algorithm for Test Set
测试集问题的集合覆盖贪心算法的深入近似

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+1 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 addition, 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.