Tag
greedy
- Jul 20, 2026 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. algorithms
- 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
- Apr 5, 2025 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. algorithms