Greedy Algorithm
The greedy algorithm for set covering chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of, where is the size of the set to be covered is the -th harmonic number:
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 (see Inapproximability results below), under plausible complexity assumptions.
Read more about this topic: Set Cover Problem
Famous quotes containing the word greedy:
“Oh mother,
her in your lap,
as good as a bowlful of clouds,
I your greedy child
am given your breast,
the sea wrapped in skin.”
—Anne Sexton (1928–1974)