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:
“I’m a very smart guy. I haven’t a feeling or a scruple in the world. All I have the itch for is money. I am so money greedy that for twenty-five bucks a day and expenses, mostly gasoline and whisky, I do my thinking myself, what there is of it; I risk my whole future, the hatred of the cops ... I dodge bullets and eat saps, and say thank you very much, if you have any more trouble, I hope you’ll think of me, I’ll just leave one of my cards in case anything comes up.”
—Raymond Chandler (1888–1959)