the greedy ln n approximation for set cover
You have a universe of n items to cover (say n cities to provide service to), and a collection of available sets (service regions, each covering some subset of cities). You want to choose as few sets as possible so that every item lands in at least one chosen set. This is set cover, and finding the minimum number of sets is NP-hard. The natural greedy rule is irresistible: keep grabbing the set that covers the most still-uncovered items.
Concretely: start with everything uncovered. Repeat — among all sets, pick the one covering the largest number of currently-uncovered items, add it to your solution, mark its items covered — until nothing is left uncovered. The clever part is the analysis. Suppose the optimum uses OPT sets. At any moment, those OPT sets together cover all remaining uncovered items, so by pigeonhole at least one of them covers at least a 1/OPT fraction of what remains; the greedy choice covers at least that much. So each step removes at least a 1/OPT fraction of the uncovered items, meaning the remaining count shrinks by a factor (1 - 1/OPT) each step. Starting from n, after roughly OPT * ln n steps the uncovered count drops below 1, i.e. to zero. So greedy uses at most about OPT * ln n sets — a guarantee of ln n times optimal (more precisely H_n = 1 + 1/2 + ... + 1/n, the n-th harmonic number, which is about ln n).
Why this matters and where it bites. Set cover is everywhere — facility placement, feature selection, sensor coverage — and greedy is both simple and the practical default. The striking fact is that this ln n is essentially the best any polynomial algorithm can do: it is NP-hard to approximate set cover better than (1 - o(1)) ln n. So unlike vertex cover (constant factor 2), set cover genuinely cannot be approximated to a constant; the logarithmic loss is unavoidable. The honest caveat: ln n is a worst-case ceiling, and on typical instances greedy is far better — but you cannot count on that, and instances forcing the full ln n loss really do exist.
Universe {1,...,8}. Sets: A={1,2,3,4,5}, B={6,7,8}, C={1,2,6}, D={3,4,7}, E={5,8}. Greedy first takes A (covers 5, the most). Remaining {6,7,8}: B covers all 3, take it. Done in 2 sets — which is also optimal here. The greedy 'most-new-coverage' rule did the right thing on this small case.
Greedy always grabs the set covering the most uncovered items; this yields an H_n ~ ln n guarantee.
Greedy's ln n is essentially optimal: beating (1 - o(1)) ln n is NP-hard, so no constant-factor approximation exists for general set cover (unlike vertex cover). The logarithmic loss is a property of the problem, not a weakness of greedy.