When is "take the best-looking option now" provably good enough?
Integer programming (topic 04) is where the corner theorem stops being enough, and branch and bound (05) is the machinery that copes. Topic 19 shares this course's language of variables and constraints but drops the objective: sometimes the honest question is not “what's best” but “does anything work at all.” Topic 21 asks when the simplest rule of thumb is provably good enough, and topic 10 is what you reach for once exact methods die.
A greedy algorithm builds a solution one commitment at a time, and each commitment is whatever looks best right now by some fixed local rule (cheapest edge, largest set, highest ratio) with no lookahead and no backtracking. It is the first thing anyone tries on a new problem, and usually the first thing they abandon, because it is so easy to build an instance where grabbing the shiny thing early forces three bad choices later.
Operations research keeps greedy in the toolkit anyway, for two precise reasons. First: on some problems greedy is not a heuristic at all. It is exactly optimal, provably, on every instance. Minimum spanning tree is the classic case: Kruskal's algorithm just adds the cheapest edge that doesn't form a cycle, forever, and the tree it ends on is the cheapest tree that exists. That is not luck. It is a structural property of the problem, the matroid property, made precise below.
Second: when greedy is not optimal, it often comes with a guarantee: a proof, worked out before you ever run it, that its answer is within a fixed factor of the best possible, no matter how adversarial the input. An algorithm that is always within 2× optimal, runs in a blink, and never needs tuning is worth a great deal, especially as the honest baseline a fancier method has to beat. This is the same role simulated annealing plays for quantum annealing in the bridges section below: you cannot claim a win without knowing what the cheap classical method already gets for free.
Greedy is also the degenerate corner of topic 10's picture: a metaheuristic with the exploration turned all the way off. Simulated annealing at zero temperature is greedy descent. Every method in that topic exists precisely because pure greed gets stuck, but knowing exactly how badly it can get stuck, as a theorem, is what tells you whether the extra machinery is worth it.
When greedy is exactly optimal: matroids. An independence system is a ground set E with a family of “independent” subsets closed under taking subsets. It is a matroid if it also satisfies the exchange property: whenever independent sets A and B have |A| < |B|, some element of B\A can be added to A keeping it independent. Rado (1957) and Edmonds (“Matroids and the Greedy Algorithm,” Mathematical Programming 1, 127–136 (1971)) proved the sharp statement: the greedy algorithm returns a maximum-weight independent set for every weighting if and only if the independence system is a matroid. Forests of a graph form a matroid (the graphic matroid), which is exactly why Kruskal's cheapest-edge rule is optimal for minimum spanning tree, and why the same trick fails for shortest path or the travelling salesman, whose feasible structures are not matroids.
When greedy is not optimal: the approximation ratio. For a minimisation problem, an algorithm is a ρ-approximation if on every instance it returns a solution of cost at most ρ times the optimum, with ρ fixed and known ahead of time. For set cover, greedy's ratio is the harmonic number:
greedy sets ≤ H(k) · OPT , H(k) = 1 + 1/2 + 1/3 + ⋯ + 1/k ≈ ln k
k = size of the largest set
proved by Johnson (1974), Lovász (1975) and Chvátal (1979). The proof is a charging argument: when greedy covers a batch of new elements, charge 1/(batch size) to each; every set in the optimal cover absorbs at most H(k) in total charge, so greedy's count is at most H(k) · OPT. And this is essentially the best any polynomial-time algorithm can do. Feige (“A Threshold of ln n for Approximating Set Cover,” Journal of the ACM 45(4), 634–652 (1998)) proved no polynomial algorithm achieves (1 − ε) ln n unless every NP problem has a slightly-superpolynomial algorithm; Dinur & Steurer (2014) removed the last caveat. Greedy is essentially optimal for set cover: no polynomial algorithm can improve on its leading ln n factor by any constant, and greedy itself attains ln n + O(1).
The submodular generalisation. The reason set cover has such a clean bound is that its coverage function is submodular: adding an element to a smaller collection helps at least as much as adding it to a larger one: diminishing returns, made formal. Nemhauser, Wolsey & Fisher (“An Analysis of Approximations for Maximizing Submodular Set Functions. I,” Mathematical Programming 14, 265–294 (1978)) proved that for maximising any monotone submodular function under a “pick at most m items” constraint, greedy is a (1 − 1/e)-approximation: at least 63.2% of optimal. Nemhauser & Wolsey (“Best Algorithms for Approximating the Maximum of a Submodular Set Function,” Mathematics of Operations Research 3, 177–188 (1978)) then showed that in the value-oracle model no polynomial-query algorithm beats 1 − 1/e, and Feige (1998) showed the same barrier holds for maximum coverage unless P = NP. That bound now underwrites sensor placement, feature selection, influence maximisation and data summarisation across the field. (The verification script confirms this page's instance is submodular by checking the diminishing-returns inequality on every nested pair of collections.)
Where greedy has no constant guarantee at all: 0/1 knapsack (topic 05's and The Prune's problem). Sorting items by value-to-weight ratio and taking them greedily can be arbitrarily far from optimal. One heavy, slightly-better-ratio item can crowd out a perfect fill. The repair is almost embarrassingly small: return the better of the greedy pack and the single most valuable item that fits, and you have a 1/2-approximation (Sahni, “Approximate Algorithms for the 0/1 Knapsack Problem,” Journal of the ACM 22(1), 115–124 (1975)). Scaling and rounding the item values instead gives a fully polynomial-time approximation scheme: optimal to any ε you name, in time polynomial in both n and 1/ε: the first for knapsack being Ibarra & Kim (“Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems,” Journal of the ACM 22(4), 463–468 (1975)). Verification: a script recomputes this.
Every compression you have ever used Huffman coding builds an optimal prefix-free code by a pure greedy rule (repeatedly merge the two least-frequent symbols) and the code it produces is provably minimum-redundancy (Huffman, 1952). It is inside ZIP, PNG, JPEG, MP3 and HTTP/2 header compression. This is a greedy algorithm that is exactly optimal, not through matroid structure this time, but by a direct exchange argument: the two least-frequent symbols can always be taken as the deepest pair in some optimal tree, and induction on the merged instance does the rest.
Inside a quantum computer's real-time decoder Topic 07 showed that decoding the surface code is minimum-weight perfect matching. Exact matching is fast but not quite fast enough at scale, so a widely used alternative is the Union–Find decoder (Delfosse & Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum 5, 595 (2021)): it greedily grows clusters of flipped syndromes until each can be explained, trading a small loss of accuracy (measured empirically, not bounded by a theorem) for a provably almost-linear runtime. It is a greedy approximation to the exact matcher, chosen for exactly the reason this topic exists: a fast, well-tested approximation beats an exact method you cannot afford to run in the microsecond you have. See the exact matcher lose a different way: the Decoder Duel →
Check yourself
Kruskal's cheapest-edge rule is exactly optimal for the minimum spanning tree. What structural property guarantees it?
Rado and Edmonds proved greedy is optimal for every weighting if and only if the independence system is a matroid. The same trick fails for shortest path and the travelling salesman.