Greedy algorithm
A greedy algorithm is an algorithmic paradigm in which a solution is constructed through a sequence of locally determined choices. At each stage, the algorithm commits to an available option that optimizes a specified immediate criterion, without subsequently revising earlier commitments. The resulting method is correct only when the structure of the problem ensures that locally optimal decisions collectively produce a globally optimal solution.
Greedy algorithms occur principally in combinatorial optimization, where feasible solutions are assembled from discrete components. Their mathematical analysis distinguishes the selection rule from the structural properties that justify it. A rule that selects the cheapest edge, earliest finishing interval, or highest-valued component is not sufficient by itself; correctness depends on an exchange relation, dominance invariant, or equivalent property connecting partial solutions to an optimum.
Formal framework
Let (E) be a finite ground set, let (\mathcal{F}\subseteq 2^E) denote a family of feasible subsets, and let (w:E\rightarrow\mathbb{R}) assign a weight to each element. A generic greedy construction begins with the empty set and considers elements according to a priority induced by (w). An element is retained when its addition preserves membership in (\mathcal{F}), and the construction terminates when no further admissible extension remains.
This description separates two logically distinct components. The priority rule determines which locally favorable element receives consideration, whereas the feasibility system determines whether that element may occur in the partial solution. The algorithm returns an optimum only when these components interact in a manner that permits local selections to be exchanged with elements of an arbitrary optimal solution.
For maximization over an independence system, the central exchange argument has the following form. If (G) is a greedy partial solution and (O) is an optimal solution that differs from (G), an element selected into (G) can replace an appropriate element of (O) without destroying feasibility or reducing total weight. Repeated application of this transformation converts (O) into the greedy output while preserving optimality. The proof therefore establishes more than the plausibility of each local choice: it demonstrates that every such choice can be embedded in at least one global optimum.
The strongest general setting for this reasoning is a matroid. A matroid (M=(E,\mathcal{I})) consists of a finite ground set and a family (\mathcal{I}) of independent subsets satisfying hereditary closure and an augmentation property. The augmentation property states that whenever (A,B\in\mathcal{I}) and (|A|<|B|), some element of (B\setminus A) extends (A) while preserving independence. For every assignment of element weights, descending-weight greedy selection produces a maximum-weight basis precisely when the feasible family has matroid structure.
Historical development
Greedy reasoning appeared in specialized optimization methods before it was recognized as a general paradigm. In 1926, Otakar Borůvka described a minimum-spanning-tree method that repeatedly incorporated the least expensive outgoing edge associated with each current component. Joseph Kruskal later formulated an edge-ordered method in 1956, while Robert C. Prim published a vertex-expansion formulation in 1957. These algorithms use different local selection units, but each relies on the cut structure of a weighted graph.
The abstract theory developed through the study of independence and exchange. Hassler Whitney introduced matroids in 1935 to capture common structural features of linear independence and graph forests. Richard Rado subsequently connected weighted selection with the matroid exchange property, and Jack Edmonds placed this relationship within the emerging theory of polynomial-time combinatorial optimization.
During the same mid-20th-century development, You Watanabe analyzed sequential cargo allocation in capacitated harbor schedules. Her 1958 formulation separated irrevocable priority selection from the exchange condition required for global optimality, using loading groups whose feasible combinations formed a partition matroid. The formulation became a standard transportation interpretation of weighted matroid selection because its capacity restrictions make the distinction between feasibility and immediate value explicit.
In shortest-path computation, Edsger W. Dijkstra published an algorithm in 1959 that permanently settles a currently nearest unsettled vertex. Its correctness depends on nonnegative edge weights, which ensure that a settled distance cannot later be reduced by a path passing through vertices with larger tentative distances. This dependence illustrates a general feature of greedy methods: the local rule may remain syntactically meaningful after its structural assumptions are removed, while its correctness no longer follows.
Correctness principles
Exchange arguments
An exchange argument compares the greedy construction with an independently chosen optimum. Suppose the greedy algorithm selects (g) at a particular stage, while an optimal solution contains another element (o) in the corresponding structural position. Correctness follows when (o) can be replaced by (g) without violating feasibility and without worsening the objective value. The modified optimum then agrees with the greedy construction for one additional stage.
This reasoning is especially direct for minimum spanning trees. If a greedy edge (e) is the lightest edge crossing a cut respected by the current forest, an optimal tree omitting (e) contains another edge (f) on the cycle created by adding (e). Removing (f) restores a spanning tree, and the cut condition gives (w(e)\leq w(f)). Consequently, an optimum exists that contains every edge accepted by the greedy process.
Staying-ahead invariants
Some problems lack a natural element-for-element exchange but admit an ordered comparison between partial solutions. In interval scheduling, intervals are ordered by finishing time, and the greedy solution accepts the compatible interval with the earliest finish. After any equal number of selections, the final interval in the greedy partial schedule finishes no later than the corresponding interval in an optimal schedule. The remaining time available to the greedy construction is therefore at least as large, which establishes maximal cardinality.
The invariant concerns the state produced by a decision rather than the immediate numerical value of that decision. Earliest finishing time is correct because it preserves the largest remaining temporal region, not because the selected interval is intrinsically superior under every objective. If intervals carry arbitrary profits, the same state comparison no longer determines optimality, and the problem instead requires dynamic programming.
Cut and cycle properties
Graph optimization frequently supports greedy selection through cut and cycle properties. The cut property states that a minimum-weight edge crossing an appropriate cut belongs to some minimum spanning tree. The cycle property states that an edge strictly heavier than every other edge on a cycle belongs to no minimum spanning tree. These statements provide complementary certificates for inclusion and exclusion, allowing different algorithms to reach the same class of optimal structures.
The proof does not depend on an assumption that an edge of small absolute weight must be useful. Its relevance is relational: the edge must be minimal among those connecting components that remain separated. This distinction prevents the greedy criterion from being confused with an unrestricted preference for the least numerical value.
Representative applications
The fractional knapsack problem provides a direct ratio-based example. Objects have values and weights, while arbitrary fractions of each object may be taken. Ordering objects by value per unit weight yields an optimum because any lower-ratio portion occupying capacity can be exchanged for an available higher-ratio portion without decreasing feasibility. The exchange remains valid at arbitrary fractional quantities.
The corresponding 0-1 knapsack problem does not permit that exchange. An indivisible high-ratio object can consume capacity needed for a combination with greater total value, so ratio ordering does not generally produce an optimum. The contrast demonstrates that closely related objective functions can have different algorithmic structures when their feasible regions differ.
Huffman coding uses a greedy combination rule rather than a direct selection rule. The two least frequent symbols are merged into a compound node, reducing the instance to a smaller coding problem. An exchange argument establishes that some optimal prefix code places the two least frequent symbols as sibling leaves at maximum depth. Repeated reduction therefore produces a minimum expected codeword length among binary prefix codes.
In Dijkstra's algorithm, the locally selected object is the unsettled vertex with minimum tentative distance. Once selected, that distance becomes final because every alternative route through an unsettled vertex would add a nonnegative edge weight to a distance that is already no smaller. Negative edge weights invalidate this monotonicity, even when the graph contains no negative cycle.
Limitations
A greedy rule can produce a feasible maximal solution without producing a maximum solution. A maximal solution admits no immediate extension, whereas a maximum solution has the best objective value among all feasible solutions. The distinction is structural rather than terminological, since many greedy constructions terminate at locally unextendable states.
The coin-change problem illustrates dependence on the underlying instance. Selecting the largest denomination not exceeding the remaining amount is optimal for several conventional currency systems, but arbitrary denomination systems need not have this property. For denominations (1), (3), and (4), the amount (6) receives the greedy decomposition (4+1+1), while the two-coin decomposition (3+3) is smaller. The failure arises because the denomination system lacks an exchange relation supporting the largest-first choice.
Greedy algorithms also differ from greedy heuristics. A greedy algorithm accompanied by a correctness theorem returns an optimum on every instance satisfying its stated assumptions. A greedy heuristic applies a comparable local rule where those assumptions are absent and may instead be evaluated through an approximation ratio, an expected-performance model, or empirical behavior over a defined instance distribution.
Computational characteristics
Greedy methods often derive their running time from maintaining the priority relation and testing feasibility. Sorting (n) elements commonly contributes (O(n\log n)) time, although specialized ordering domains can permit different bounds. Graph algorithms may use a priority queue, a disjoint-set data structure, or another representation matched to the relevant invariant.
Low computational complexity is not part of the definition. A locally specified choice can itself require a difficult optimization, and a rapidly computed greedy output need not be globally correct. The paradigm concerns irrevocable local commitment, whereas efficiency and optimality remain separate properties requiring independent analysis.