Mathematics
Matroids and Their Role in Optimization
Quick fact
The greedy algorithm finds the optimal basis for any weighted matroid, meaning if a problem's feasible sets form a matroid, the simple 'pick the best next element' strategy is guaranteed to be optimal.
Why this is interesting
Ever wondered why the same greedy approach works for finding cheapest networks and choosing independent vectors? The answer lies in a hidden structure called a matroid.