all of the left-vertices, which is precisely the Hitting set problem. Greedy algorithm There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a bucket queue to prioritize the sets. It achieves an approximation ratio of , where is the size of the set to be covered. In other words, it finds a covering that may be times as large as the minimum one, where is the -th harmonic number: This greedy algorithm actually achieves an approximation ratio of where is the maximum cardinality set of . For dense instances, however, there exists a -approximation algorithm for every . There is a standard example on which the greedy algorithm achieves an approximation ratio of . The universe consists of elements. The set system consists of pairwise disjoint sets with sizes respectively, as well as two additional disjoint sets , each of which contains half of the elements from each . On this input, the greedy algorithm takes the sets , in that order, while the optimal solution consists only of and . An example of such an input for is pictured on the right. Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results below), under plausible complexity assumptions. A tighter analysis for the greedy algorithm shows that the approximation ratio is exactly . Low-frequency systems If each element occurs in at most sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of using LP relaxation. If the constraint is replaced by for all in in the integer linear program shown above, then it becomes a (non-integer) linear program . The algorithm can be described as follows: Find an optimal solution for the program using some polynomial-time method of solving linear programs. Pick all sets for which the corresponding variable has value at least 1/ in the solution . Inapproximability results When refers to the size of the universe, showed that set covering cannot be approximated in polynomial time to within a factor of , unless NP has quasi-polynomial time algorithms. Feige (1998) improved