Algorithms · Cluster
Greedy and Approximation
Exchange arguments, matroids, and ratio guarantees.
- 01 The Exchange Argument: Proving a Greedy Choice Is Safe How replacing the first divergence between an optimal solution and a greedy one establishes correctness, and why the same swap fails on problems like 0/1 knapsack.
- 02 Earliest-Finish-First for Interval Scheduling Why sorting intervals by finishing time and accepting each compatible one yields a maximum set, and why sorting by start time or by length does not.
- 03 Huffman Coding and the Greedy Merge How repeatedly merging the two lowest-weight nodes builds an optimal prefix code, what the sibling-property exchange shows, and where the code length bound comes from.
- 04 Matroid Structure and the Exact Boundary of Greedy Optimality The independence axioms that make greedy weight-ordering optimal, how spanning trees and interval scheduling fit them, and the obstruction that knapsack exhibits.
- 05 Fractional Relaxation and the Knapsack Integrality Gap Why the density-ordered greedy rule is exactly optimal for fractional knapsack, how the 0/1 version loses a factor of two, and what value scaling buys back.
- 06 Kruskal, the Cut Property, and Why Any Minimum Edge Is Safe The cut and cycle properties that justify sorting edges by weight, how the proof differs from a plain exchange, and what happens when weights tie.
- 07 The Harmonic Bound for Greedy Set Cover How cost-per-new-element selection yields an H(n) approximation, why that bound is tight, and what the frequency parameter changes.
- 08 Christofides: Matching the Odd Vertices to Reach 3/2 Why doubling a minimum spanning tree gives a factor of 2, how a minimum-weight matching on the odd-degree vertices recovers the remaining half, and where the metric assumption is spent.
- 09 The Primal-Dual Schema: Dual Variables as a Certificate How charging primal costs against a feasible dual solution yields approximation guarantees for facility location and prize-collecting problems, without solving an LP.
- 10 Gap Amplification and Why Some Ratios Cannot Be Improved How the PCP theorem turns a gap in a constraint system into an inapproximability result, and what that means for the approximation ratios of the algorithms it bounds.