Tag
approximation-ratio
- 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
- Jun 27, 2024 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. algorithms
- May 27, 2024 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. algorithms
- Feb 24, 2022 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. algorithms