A Tighter Analysis of Setcover Greedy Algorithm for Test Set

Details A Tighter Analysis of Setcover Greedy Algorithm for Test Set A Tighter Analysis of Setcover Greedy Algorithm for Test Set

2007-05-12

arxiv.org/abs/0705.1750v6

Computer Science

Data Structures and Algorithms

12 pages, 3 figures, Revised version

Scientific paper

Setcover greedy algorithm is a natural approximation algorithm for test set problem. This paper gives a precise and tighter analysis of performance guarantee of this algorithm. The author improves the performance guarantee $2\ln n$ which derives from set cover problem to $1.1354\ln n$ by applying the potential function technique. In addition, the author gives a nontrivial lower bound $1.0004609\ln n$ of performance guarantee of this algorithm. This lower bound, together with the matching bound of information content heuristic, confirms the fact information content heuristic is slightly better than setcover greedy algorithm in worst case.

Affiliated with

Also associated with

No associations

Rating

A Tighter Analysis of Setcover Greedy Algorithm for Test Set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Tighter Analysis of Setcover Greedy Algorithm for Test Set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Tighter Analysis of Setcover Greedy Algorithm for Test Set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-620792