A Tighter Analysis of Set Cover Greedy Algorithm for Test Set

摘要

Set cover greedy algorithm is a natural approximation algorithm for test set problem. This paper gives a precise and tighter analysis of approximation ratio of this algorithm. The author improves the approximation ratio 2 ln n directly derived from set cover to 1.14 lnn by applying potential function technique of derandomization method. In addition, the author gives a nontrivial lower bound (1 + α) ln n of approximation ratio, where α is a positive constant. This lower bound, together with the matching bound of information content heuristic, confirms the fact information content heuristic is slightly better than set cover greedy algorithm in worst case.