Tag
exchange-argument
- Nov 28, 2025 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. algorithms
- Aug 4, 2025 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. algorithms
- Jul 24, 2025 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. algorithms