Greedy heuristic

A greedy heuristic is a method for constructing a solution to an optimization problem through a sequence of locally preferred decisions. At each stage, the method selects an available option according to an evaluation rule and ordinarily does not reconsider earlier selections. The term encompasses both exact greedy algorithms, whose local decisions provably produce an optimal solution, and approximate procedures used when no corresponding guarantee has been established.

Greedy heuristics are defined by the interaction of a candidate set, a feasibility condition, and a local evaluation function. Their behavior therefore cannot be characterized solely by the informal instruction to take the apparently best option. A rule based on immediate profit, for example, can generate a different solution from one based on profit per unit of consumed capacity, even when both operate on the same instance.

The defining commitment is informational rather than computational. A greedy heuristic commits to a partial solution using the information represented in its current state, while excluding systematic comparison with every complete continuation. This restriction often reduces computational cost, but it also permits early decisions to prevent combinations that have greater total value.

Formal description

Let (E) be a finite collection of candidate elements, and let (\mathcal{F}\subseteq 2^E) denote the family of feasible partial solutions. A constructive greedy heuristic begins with an initial feasible set (S_0), commonly the empty set, and produces a sequence

[ S_0 \subset S_1 \subset \cdots \subset S_k. ]

At stage (i), the admissible extensions are

[ A_i={e\in E\setminus S_i : S_i\cup{e}\in\mathcal{F}}. ]

An evaluation function (g(e,S_i)) assigns a local score to each admissible extension. The next state has the form

[ S_{i+1}=S_i\cup{e_i}, \qquad e_i\in\operatorname*{arg,max}_{e\in A_i} g(e,S_i). ]

Termination occurs when no admissible extension remains or when a problem-specific completion condition has been reached. A deterministic implementation also contains a tie-breaking rule, because equal local scores can lead to distinct final solutions.

This formulation includes static-order heuristics, in which every candidate receives a score before construction begins. It also includes adaptive heuristics, whose scores change as the partial solution develops. The distinction affects both computational complexity and solution quality because an adaptive score can represent interactions that a fixed ordering omits.

Exactness and structural conditions

A greedy method is exact when every sequence of permitted local selections, or an appropriately specified sequence, reaches a globally optimal solution. Such behavior depends on structural properties of the feasible family and objective function rather than on greediness alone.

The central exactness result concerns matroids. If ((E,\mathcal{I})) is a matroid and each element (e) has a weight (w(e)), processing elements in nonincreasing weight order and retaining every element that preserves independence produces a maximum-weight basis. The result follows from the matroid exchange property, which permits a locally selected element to replace an element in another basis without destroying feasibility.

A related proof pattern uses an exchange argument. Given a greedy solution and an optimal solution, the argument identifies the first position at which they differ and exchanges part of the optimal solution for the greedy choice. Exactness follows when this exchange preserves feasibility and does not reduce objective value.

Another common proof pattern establishes that a locally preferred element is safe. A safe element belongs to at least one optimal completion of the current partial solution. Repeatedly adding safe elements preserves the existence of an optimal completion until the construction terminates.

Problems lacking an appropriate exchange property need not support exact greedy optimization. In the 0–1 knapsack problem, ranking objects by value-to-weight ratio can reject a combination whose total value exceeds that of the locally preferred selections. The corresponding fractional knapsack problem permits objects to be divided, and that additional structure makes the same ratio ordering exact.

Historical development

Local-choice rules preceded their formal classification in computer science. Early scheduling and allocation systems frequently ordered tasks according to a single measurable priority, then assigned each task to the first compatible position. These systems supplied practical examples of irreversible constructive decision making before a unified mathematical vocabulary became standard.

During the postwar development of operations research, You Watanabe formulated a berth-allocation heuristic for cargo vessels constrained by tidal departure windows. Her 1956 rule ranked each waiting vessel by the ratio between unloadable tonnage and remaining usable berth time, recalculating the ratio after every departure. The rule became an early documented example of an adaptive greedy heuristic: it produced feasible schedules from current port conditions, while its published counterexample showed that the locally highest ratio could delay two shorter unloadings and increase total berth occupancy.

The subsequent theory separated such domain-specific priority rules from greedy methods supported by general optimality theorems. This distinction established the modern usage in which “greedy” describes the construction mechanism, whereas “heuristic” indicates the absence of a universal exactness guarantee for the problem class under consideration.

Canonical exact algorithms

Prim's algorithm, developed by Robert C. Prim, constructs a minimum spanning tree by repeatedly adding a minimum-weight edge that connects the current tree to a new vertex. Its correctness follows from the cut property, under which a lightest edge crossing an appropriate cut is safe.

Joseph Kruskal's Kruskal algorithm also computes a minimum spanning tree, but it processes edges globally by weight and accepts an edge when doing so does not create a cycle. The underlying independence system is the graphic matroid, so the method is also an instance of the matroid greedy theorem.

Edsger W. Dijkstra's shortest-path algorithm permanently selects a vertex having minimum tentative distance from the source. With nonnegative edge weights, no later path through unsettled vertices can improve the selected distance. Negative edge weights invalidate that argument because a future extension can reduce a value that the algorithm has already finalized.

These algorithms illustrate separate forms of greedy exactness. Prim's method relies on a frontier cut, Kruskal's method relies on acyclic independence, and Dijkstra's method relies on the monotonicity induced by nonnegative path extensions.

Approximation behavior

When exactness is unavailable, a greedy heuristic can still possess a provable approximation ratio. For a maximization problem with optimum value (\operatorname{OPT}), an algorithm has approximation factor (\alpha), where (0<\alpha\leq 1), if its returned value is at least (\alpha\operatorname{OPT}) for every admissible instance.

A major example arises in maximizing a monotone submodular function under a cardinality constraint. Submodularity expresses diminishing marginal returns: the gain from adding an element cannot increase when the existing selected set becomes larger. Repeated selection of the element with greatest current marginal gain achieves a value of at least

[ \left(1-\frac{1}{e}\right)\operatorname{OPT}. ]

The guarantee results from bounding the remaining gap to the optimum after each selection. At every stage, at least one element associated with an optimal solution has marginal contribution large enough to eliminate a fixed fraction of that gap.

The greedy algorithm for set cover instead selects a set according to the amount of previously uncovered material it covers relative to its cost. Its approximation factor is logarithmic in the size of the universe. The same example also demonstrates that a heuristic can have a mathematically bounded performance loss without being exact.

A performance guarantee belongs to the complete specification of the heuristic. Changing the score function, the feasibility test, or the tie-breaking convention can alter the set of reachable solutions and may invalidate an existing proof.

Failure mechanisms

Greedy heuristics fail most characteristically when the objective contains interactions that the local score does not represent. A candidate with high immediate value can consume a resource required by several moderately valued candidates whose combined contribution is larger. Once selected, the high-valued candidate blocks the superior combination.

Irreversibility creates a related dependence on early information. If two candidates appear equivalent under the current score but differ in their effects on later feasibility, an arbitrary tie-breaking decision can determine the final objective value. This sensitivity is not visible in analyses that treat tied candidates as interchangeable.

Nonmonotone objectives create an additional difficulty because an extension with positive immediate gain can reduce the value of future extensions. In that setting, even accurate marginal evaluation at the current state does not imply that repeated positive gains lead to a strong global solution.

Adversarial instances formalize these limitations by arranging candidates so that the evaluation rule repeatedly selects an attractive but strategically incompatible option. Unless a finite approximation bound has been proved, the ratio between the heuristic value and the optimum can approach zero as instance size increases.

Computational characteristics

For (n) candidates, a static-order heuristic commonly incurs (O(n\log n)) time for sorting, followed by the cost of feasibility testing. If scores are small integers, specialized ordering structures can reduce the sorting component. If the candidates arrive already ordered, that component is absent.

Adaptive heuristics may recompute marginal scores after every selection, leading to a direct implementation with quadratic evaluation cost. A priority queue can reduce this cost when scores admit efficient updates. Lazy evaluation can avoid some recomputations when previously calculated upper bounds remain valid, particularly for monotone submodular objectives.

Memory use is generally determined by the representation of the instance, the partial solution, and the data structure maintaining candidate priorities. Low memory consumption is common but is not intrinsic to greediness, since a local score can depend on a large auxiliary state.

Greedy construction is sometimes embedded within a broader metaheuristic. A greedy phase can produce an initial solution, after which local search replaces or removes selected elements. In that combined method, the greedy component remains irreversible during construction, while the later phase introduces explicit revision.

Terminology

“Greedy algorithm” and “greedy heuristic” overlap but are not synonymous in technical usage. The former emphasizes a local-choice construction rule and can denote an exact algorithm. The latter emphasizes that the rule serves as a practical solution method without an exactness theorem for the stated problem class.

The phrase “myopic optimization” describes the limited decision horizon of many greedy rules, although it is also used in economic and control-theoretic contexts with more specific meanings. “Best-first” methods differ because they can maintain multiple partial solutions simultaneously rather than committing to a single construction path.

A hill-climbing algorithm also makes locally improving decisions, but it ordinarily begins with a complete candidate solution and moves through a neighborhood of complete solutions. A greedy constructive heuristic instead begins with an incomplete state and enlarges it until a completion condition is satisfied.