Set Cover: given a universe U and a family of subsets, find the minimum number of subsets whose union covers U. It is NP-hard and the greedy algorithm — always pick the set covering the most uncovered elements — achieves a H(n) ≈ ln(n) approximation ratio, which is optimal: no polynomial algorithm can do better unless NP ⊆ DTIME(n^(log log n)) (Feige 1998). The LP relaxation has an integrality gap of Θ(log n). Set cover models feature selection, network monitoring placement, and the general resource allocation problem underlying many NP-hard optimization tasks.