this lower bound to under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. established a lower bound of , where is a certain constant, under the weaker assumption that PNP. A similar result with a higher value of was recently proved by . showed optimal inapproximability by proving that it cannot be approximated to unless PNP. Weighted set cover Relaxing the integer linear program for weighted set cover stated above, one may use randomized rounding to get an -factor approximation. Non weighted set cover can be adapted to the weighted case. Related problems Hitting set is an equivalent reformulation of Set Cover. Vertex cover is a special case of Hitting Set. Edge cover is a special case of Set Cover. Geometric set cover is a special case of Set Cover when the universe is a set of points in and the sets are induced by the intersection of the universe and geometric shapes (e.g., disks, rectangles). Set packing Maximum coverage problem is to choose at most k sets to cover as many elements as possible. Dominating set is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown to be NP complete through a reduction from Set cover. Exact cover problem is to choose a set cover with no element included in more than one covering set. Red Blue Set Cover. Set-cover abduction. Notes References . . . . . External links Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination A compendium of NP optimization problems - Minimum Set Cover Families of sets NP-complete problems Linear programming Approximation algorithms Covering problems