Abstract: A randomized approximation algorithm for the set cover problem was proposed. Given a collection S of subsets of E={e1,e2,…,en} with weights on the subsets, the goal of the weighted set cover problem is to cover all the elements of E by picking a subset with the minimum total cost from S .For each uncovered element of the set E, a subset which contains the element was chosen with a certain elaborately designed probability distribution. The algorithm will not terminate until all the elements have been covered. The proposed algorithm computes a cover whose expected cost is at most B·opt where opt is the cost of some optimal cover for the problem, where B=maxe∈E{|L(e)|} and L(e)={s|e∈s,s∈S}. The running time of the algorithm is O(n) where n is the cardinality of E.

Key words: computer application, randomized algorithm, approximation algorithm, set cover