Greedy Algorithm

Greedy algorithm is an algorithmic optimization paradigm within computation and algorithms that builds a solution to a combinatorial problem incrementally through a sequence of myopic, irrevocable decisions—selecting at each step the feasible option that offers the best local improvement in the objective function without backtracking over past choices. Because a greedy algorithm commits to a single decision at each stage and reduces the problem to a single smaller subproblem (typically after an O(n log n) sorting pass or inside a priority-queue loop), it avoids the multi-dimensional state tables of dynamic programming and the branching recursion trees of a divide-and-conquer algorithm.

For general combinatorial optimization problems within computational complexity theory, locally optimal choices do not always yield a globally optimal solution. However, a foundational structural theory—initiated by Hassler Whitney's introduction of matroids in 1935 and completed by Richard Rado (1957) and Jack Edmonds (1971)—proves that greedy optimization finds the global optimum across all nonnegative weight assignments if and only if the feasible set system forms a matroid (or greedoid). Even on NP-hard problems such as Set Cover or monotone submodular maximization, greedy algorithms achieve tight polynomial-time approximation ratios bounded by harmonic numbers H(n) ≈ ln n or Euler's constant (1 − e⁻¹ ≈ 0.6321).

Greedy-Choice Property and Optimal Substructure

For a greedy algorithm to return a globally optimal solution, the problem must satisfy two structural properties:

1. Optimal Substructure: An optimal solution to the problem instance contains within it optimal solutions to the residual subproblem left behind after a decision is made.
2. Greedy-Choice Property: There exists at least one globally optimal solution S^* that includes the first locally optimal ("greedy") choice g₁. Whereas dynamic programming must solve candidate subproblems before choosing the initial transition, a greedy algorithm selects g₁ first using local information alone and then solves the single remaining subproblem.

Exchange Arguments and Fractional vs. 0–1 Knapsack

Correctness proofs for greedy algorithms typically use an exchange argument: given an arbitrary optimal solution O^* that differs from the greedy solution G, identify the first greedy element g_r ∉ O^* and swap g_r into O^* in place of a conflicting element o_r ∈ O^*. Using the greedy selection rule, one proves that the modified solution O′ = (O^* \ {o_r}) ∪ {g_r} remains feasible and has objective value no worse than O^*; repeating this swap inductively converts O^* into G.

The boundary between greedy and dynamic-programming problems is illustrated by the Knapsack Problem over n items with weights w_i, values v_i, and capacity W:

• Fractional Knapsack (Greedy Optimal in O(n log n)): When continuous fractions x_i ∈ [0, 1] are permitted, sorting items by descending value-to-weight density v_i / w_i and taking maximum shares of the highest-density items is globally optimal.
• 0–1 Knapsack (Greedy Fails): When items are indivisible (x_i ∈ {0, 1}), greedy density choice leaves unfillable capacity gaps (for W = 50 and items (10, 60), (20, 100), (30, 120), greedy picks 10 + 20 for value 160, whereas optimal 0–1 picks 20 + 30 for value 220).

Hassler Whitney's Matroid Axioms (1935) and the Rado–Edmonds Theorem (1957–1971)

In 1935, Hassler Whitney introduced matroids to unify linear independence in vector spaces and cycle-freeness in graphs. A finite matroid is a pair M = (E, ℐ) consisting of a ground set E and a family ℐ ⊆ 2^E of independent subsets satisfying three axioms:

1. Non-Emptiness: ∅ ∈ ℐ.
2. Hereditary Property: If B ∈ ℐ and A ⊆ B, then A ∈ ℐ.
3. Exchange (Augmentation) Property: If A, B ∈ ℐ with |A| < |B|, there exists some element x ∈ B \ A such that A ∪ {x} ∈ ℐ.

By the Exchange Property, all maximal independent sets (bases) of a matroid have identical cardinality rank(M). In a graphic matroid, E is the edge set of an undirected graph G and ℐ is the family of acyclic edge subsets (forests).

Given a hereditary system (E, ℐ) and nonnegative weights w : E → ℝ_≥0, the matroid greedy algorithm sorts E in non-increasing weight order w(e₁) ≥ ··· ≥ w(e_m), sets S ← ∅, and adds e_i to S whenever S ∪ {e_i} ∈ ℐ. The Rado–Edmonds Theorem proves that this greedy procedure finds a maximum-weight independent set for every nonnegative weight function w if and only if (E, ℐ) is a matroid (yielding Kruskal's minimum spanning tree algorithm on graphic matroids).

Interval Scheduling, Huffman Entropy Coding, and Submodular Optimization

1. Earliest-Finish-Time Interval Scheduling: Given n activities [s_i, f_i), sorting by earliest finish time (f₁ ≤ ··· ≤ f_n) and iteratively selecting the first compatible activity (s_i ≥ f_last) leaves the maximum remaining horizon [f_i, ∞) and achieves maximum cardinality in O(n log n) time.
2. Huffman Prefix-Free Coding (1952): Given symbol probabilities p₁, ..., p_n, David Huffman's algorithm repeatedly merges the two lowest-probability nodes in a min-heap into a parent of probability p(x) + p(y), minimizing expected codeword length L̄ = ∑ p_i l_i within 1 bit of Shannon entropy (H(X) ≤ L̄ < H(X) + 1).
3. Submodular Maximization and Bioinformatics: For any monotone submodular function f : 2^E → ℝ_≥0 (satisfying diminishing marginal returns), George Nemhauser, Laurence Wolsey, and Marshall Fisher (1978) proved that greedily picking k elements by largest marginal gain achieves f(S_k) ≥ (1 − (1 − 1/k)^k) f(OPT) ≥ (1 − e⁻¹) f(OPT) ≈ 0.6321 f(OPT). In bioinformatics, greedy agglomeration drives progressive multiple sequence alignment guide trees and neighbor-joining phylogenetic tree reconstruction.

How can you tell whether a greedy heuristic might fail on a new problem?

Test whether a locally attractive choice can block two slightly smaller choices whose combined value exceeds the single greedy pick. In unweighted interval scheduling, earliest finish time is always optimal; when intervals carry arbitrary positive weights, a short early interval of weight 1 can block a longer interval of weight 100, requiring weighted interval dynamic programming.

Why does greedy coin change work for U.S. coins {1, 5, 10, 25} but fail for arbitrary coin systems?

In a canonical coin system like {1, 5, 10, 25}, repeatedly picking the largest coin ≤ the remaining amount always minimizes coin count. For a non-canonical system like {1, 3, 4} with target 6, greedy picks 4 + 1 + 1 (3 coins), whereas the optimum is 3 + 3 (2 coins).

1. Whitney, H. (1935). "On the abstract properties of linear dependence." American Journal of Mathematics, 57(3), 509–533. https://doi.org/10.2307/2371182
2. Huffman, D. A. (1952). "A method for the construction of minimum-redundancy codes." Proceedings of the IRE, 40(9), 1098–1101. https://doi.org/10.1109/JRPROC.1952.273898
3. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390
4. Edmonds, J. (1971). "Matroids and the greedy algorithm." Mathematical Programming, 1(1), 127–136. https://doi.org/10.1007/BF01584082
5. Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). "An analysis of approximations for maximizing submodular set functions—I." Mathematical Programming, 14(1), 265–294. https://doi.org/10.1007/BF01588971