Lesson 257
Combinatorial Optimization
matroids · greedy · submodularity · LP relaxation
1:00How three structural pillars — matroids, submodularity, and integral polytopes — let greedy algorithms and linear programs solve hard discrete optimization problems exactly or near-optimally.
By the end, you can
- Explain why the 2ⁿ feasible-set explosion makes brute force hopeless and identify the three structural pillars that replace it.
- State both matroid axioms (downward-closure and exchange) and explain why the exchange property is what greedy needs.
- Apply the Rado–Edmonds theorem to decide whether greedy is exact, and verify it on the graphic matroid / Kruskal example.
- Explain why greedy fails on 0/1 knapsack using the exchange-property criterion.
- State the submodularity inequality and connect it to the intuition of diminishing returns.
- Cite the NWF 1 − 1/e greedy guarantee for monotone submodular maximization and state that it is tight unless P = NP.
- Describe the LP relaxation and explain when solving it exactly solves the original integer program.
- Define total unimodularity and identify which incidence matrices are TU.
- State König's theorem and derive it from LP duality on the TU matching LP.
- Explain the relax-and-round strategy and its role as a bridge to approximation algorithms.
Up next in Advanced Algorithms, Math & PL Theory
