Greedy Algorithm Design

Introduction and Context

A greedy algorithm constructs a solution incrementally. At each stage it selects the option that appears best according to a local criterion, without revisiting earlier decisions. The central question is not whether a locally attractive choice can be made efficiently, but whether that choice is compatible with an optimal global solution.

Greedy methods are important because they often transform difficult combinatorial problems into simple, efficient procedures. They are widely used in network design, scheduling, data compression, routing, resource allocation, approximation algorithms, and machine-learning infrastructure. However, a greedy algorithm is not justified merely because its decisions seem intuitive. Its correctness requires a proof based on structural properties of the problem.

A typical greedy algorithm has four elements:

1. A candidate set of possible decisions.
2. A selection rule that ranks candidates.
3. A feasibility test that determines whether a candidate can be added.
4. A stopping condition and, usually, a proof that the resulting solution is optimal.

The design discipline is therefore: identify a local rule, test it against counterexamples, formulate the required structural property, and prove correctness before implementation.

Learning Objectives

By the end of this chapter, students should be able to:

• explain the greedy-choice property and optimal substructure;
• distinguish greedy algorithms from dynamic programming and brute-force search;
• design and analyse interval scheduling, fractional knapsack, minimum spanning tree, Huffman coding, and shortest-path algorithms;
• prove greedy correctness using exchange, cut, cycle, and induction arguments;
• analyse time and space complexity, including the cost of sorting and priority-queue operations;
• identify cases in which greedy reasoning fails;
• evaluate practical, fairness, robustness, and governance implications of greedy decisions in AI and ML systems.

1. Foundations of Greedy Design

1.1 Greedy-choice property

A problem has the greedy-choice property when there exists an optimal solution beginning with a choice selected by the greedy rule. The property is stronger than saying that the greedy choice is locally best: it says that the choice can be extended to a globally optimal solution.

Suppose a problem instance is represented by I, and g is the choice selected by the algorithm. The property can be stated as:

After making g, the remaining problem must be solved optimally on the reduced instance. This leads to the second key property.

1.2 Optimal substructure

A problem has optimal substructure if an optimal solution contains optimal solutions to its subproblems. If a solution consists of a first decision g followed by a solution R to the residual problem, then an optimal overall solution requires R to be optimal for that residual problem. Otherwise, replacing R with a better residual solution would improve the overall solution.

Greedy-choice property and optimal substructure are related but not identical. Optimal substructure is also essential in dynamic programming, whereas the greedy-choice property is what permits irrevocable local decisions.

1.3 Generic scheme

A generic maximization scheme is:

GREEDY(C)
    S ← ∅
    while C is not empty do
        x ← best remaining candidate according to the selection rule
        remove x from C
        if S ∪ {x} is feasible then
            S ← S ∪ {x}
    return S

The selection rule and feasibility test depend on the problem. A greedy algorithm may sort candidates once, or may repeatedly extract the best candidate from a priority queue.

1.4 Greedy versus other paradigms

Greedy algorithms are especially attractive when decisions can be certified by an exchange argument or an invariant. Their usual running time is low, often O(n log n), but efficiency alone does not establish correctness.

2. Proof Techniques for Greedy Algorithms

2.1 Exchange argument

An exchange proof starts with an arbitrary optimal solution and transforms it into one containing the greedy choice without worsening its value. If the first greedy choice is g and an optimal solution uses another choice y in the corresponding position, replace y by g. The proof must establish both feasibility and non-inferiority of the exchange.

A common pattern is:

1. Let O be an optimal solution.
2. If O already contains g, continue with the residual problem.
3. Otherwise, identify an element y that can be replaced by g.
4. Show that the replacement remains feasible and does not reduce objective value.
5. Apply induction to the remaining instance.

2.2 Staying-ahead argument

For ordered or scheduling problems, one solution stays ahead of another if, after every step, it has no worse a relevant boundary measure. For interval scheduling, selecting the activity with earliest finishing time leaves the earliest possible completion time after each selection. This dominance supports an induction proof.

2.3 Cut and cycle properties

Graph algorithms often use structural properties of cuts and cycles. A cut divides the vertices into two nonempty sets. A crossing edge has one endpoint on each side. For a weighted undirected graph, a light edge crossing a cut is safe when it does not create a cycle with the edges already selected.

A cycle property gives the complementary reasoning: a heaviest edge on a cycle cannot be required in some minimum spanning tree when edge weights are distinct, and can be excluded in at least one minimum spanning tree in the presence of ties.

2.4 Invariants

An invariant is a statement that remains true after every iteration. For example, in Kruskal’s algorithm, the selected edges always form a forest and can be extended to a minimum spanning tree. In Dijkstra’s algorithm, every vertex removed from the priority queue has its final shortest-path distance, provided all edge weights are nonnegative.

3. Interval Scheduling

3.1 Problem definition

Given n activities, activity i has start time sᵢ and finish time fᵢ, with sᵢ < fᵢ. Two activities are compatible if their time intervals do not overlap. The objective is to select the maximum number of mutually compatible activities.

The greedy rule is to repeatedly select the compatible activity with the smallest finish time.

INTERVAL-SCHEDULE(A)
    sort activities by nondecreasing finish time
    selected ← ∅
    lastFinish ← −∞
    for each activity i in sorted order do
        if sᵢ ≥ lastFinish then
            add i to selected
            lastFinish ← fᵢ
    return selected

3.2 Worked example

Consider the activities below.

The finish-time order is A, B, C, D, E, F, G, H, I, J, K, L. Select A first, because it finishes at 4. Activities B and C conflict with A; D is compatible and finishes at 7. Activities E, F, and G conflict with D; H finishes at 11 and is compatible, followed by K, which starts at 12. The selected set is {A, D, H, K}, containing four activities.

3.3 Correctness

Let g be the activity with the earliest finish time, and let O be an optimal schedule whose first activity is o. Since g finishes no later than o, replacing o with g preserves compatibility with every activity scheduled after o. Thus there is an optimal schedule beginning with g. Once g is selected, the remaining activities are exactly those beginning at or after f_g, and the same argument applies recursively. Therefore the algorithm is optimal.

If activities are sorted, the running time is O(n log n), and the scan takes O(n). If activities are already sorted by finish time, the running time is O(n). The extra space is O(n) if a separate output set is maintained, or O(1) beyond the input and output representation.

3.4 Why plausible rules fail

Selecting the shortest activity, the activity with the fewest conflicts, or the activity that starts earliest can be suboptimal. An activity of short duration may lie in the middle of many compatible opportunities; an early-starting activity may finish very late. The relevant structural measure is earliest finishing time because it leaves the largest possible remaining time window.

4. Fractional Knapsack

4.1 Problem definition

There are n items. Item i has value vᵢ and weight wᵢ, with wᵢ > 0. A knapsack has capacity W. Fractions of items are allowed. If xᵢ is the fraction of item i selected, then 0 ≤ xᵢ ≤ 1, and the problem is:

The ratio rᵢ = vᵢ / wᵢ is value per unit weight. The greedy algorithm takes items in nonincreasing order of rᵢ, taking a full item whenever possible and a final fraction if necessary.

4.2 Worked example

Let W = 50 and:

Take items 1 and 2 fully: weight 30 and value 160. The remaining capacity is 20, so take 20/30 = 2/3 of item 3, adding value 120 × 2/3 = 80. The total value is 240.

4.3 Correctness by exchange

Suppose an optimal solution contains a positive amount of an item with lower ratio than an available item with higher ratio, while capacity is allocated to the lower-ratio item. Transfer a small weight δ from the lower-ratio item to the higher-ratio item. The value changes by:

The solution remains feasible and does not decrease in value. Repeating this exchange produces a solution ordered by nonincreasing value-to-weight ratio. Hence the greedy solution is optimal.

The algorithm takes O(n log n) time for sorting and O(1) or O(n) additional space depending on implementation. The exchange proof depends critically on divisibility. For 0–1 knapsack, where xᵢ ∈ {0,1}, ratio ordering is not generally optimal.

For example, with capacity 50 and items (value, weight) = (100, 20), (101, 51), and (150, 50), ratio ordering selects the first item, value 100, while selecting the third item gives value 150. The 0–1 problem requires dynamic programming or another method.

5. Minimum Spanning Trees

5.1 Graph model

Let G = (V, E) be a connected, undirected, weighted graph. A spanning tree contains all vertices, is connected, and has no cycle. Every spanning tree has |V| − 1 edges. A minimum spanning tree (MST) minimizes the sum of edge weights:

Weights may be positive, zero, or negative; MST greedy correctness does not require nonnegative weights.

5.2 Kruskal’s algorithm

Kruskal’s algorithm processes edges in nondecreasing weight order and adds an edge if it connects two currently separate components.

KRUSKAL(G)
    T ← ∅
    make a separate set for each vertex
    sort E by nondecreasing weight
    for each edge (u, v) in sorted E do
        if FIND(u) ≠ FIND(v) then
            add (u, v) to T
            UNION(u, v)
    return T

A disjoint-set union structure supports FIND and UNION. With path compression and union by rank or size, the total cost of set operations is O((|V| + |E|) α(|V|)), where α is the inverse Ackermann function, extremely slow-growing in practice. Sorting dominates, giving O(|E| log |E|) time.

5.3 Prim’s algorithm

Prim’s algorithm grows one tree from an arbitrary start vertex. At each step it adds the minimum-weight edge connecting the current tree to a vertex outside it. With a binary heap and adjacency lists, the running time is O(|E| log |V|); with a simple array representation for a dense graph, it is O(|V|²).

5.4 Cut-property proof

Let S be the set of edges already selected by a greedy MST algorithm, and suppose S does not contain a cycle. Consider a cut that respects S, meaning no edge in S crosses from one side of the cut to the other. Let e be a minimum-weight edge crossing that cut. The cut property states that e is safe: some MST contains S ∪ {e}.

To prove this, take an MST T containing S. If e is in T, the result follows. Otherwise, adding e to T creates a cycle. That cycle contains another edge f crossing the cut. Since e is minimum across the cut, w(e) ≤ w(f). Remove f. The result is a spanning tree containing S ∪ {e} and has weight no greater than T. It is therefore also an MST.

Kruskal and Prim are different implementations of the same safety principle. Kruskal considers the globally lightest available edge that joins components; Prim considers the lightest edge crossing the current tree’s cut.

6. Huffman Coding

6.1 Prefix codes

A prefix code assigns binary strings to symbols so that no codeword is a prefix of another. This guarantees unique, instantaneous decoding. If symbol i has frequency or probability pᵢ and codeword length ℓᵢ, the expected code length is:

where ∑ᵢ pᵢ = 1. If frequencies rather than probabilities are used, minimizing total encoded bits is equivalent to minimizing ∑ᵢ fᵢℓᵢ.

6.2 Algorithm

Huffman’s algorithm repeatedly combines the two least-frequent nodes.

HUFFMAN(symbols)
    insert every symbol and frequency into a min-priority queue Q
    while Q contains more than one node do
        x ← EXTRACT-MIN(Q)
        y ← EXTRACT-MIN(Q)
        z ← node with frequency f(x) + f(y), children x and y
        INSERT(Q, z)
    return the final tree

Assign 0 and 1 to the two branches. The time complexity is O(n log n) using a binary heap.

6.3 Example

Suppose symbols have frequencies A: 5, B: 9, C: 12, D: 13, E: 16, F: 45. Combine 5 + 9 = 14; then 12 + 13 = 25; then 14 + 16 = 30; then 25 + 30 = 55; finally 45 + 55 = 100. One valid code assignment gives F length 1, C and D length 3, and A, B, E lengths 4, 4, and 3 respectively. The total number of encoded bits is:

Different left-right assignments produce different bit strings but the same code lengths and total cost.

6.4 Correctness intuition

In an optimal prefix tree, two least-frequent symbols can be placed as sibling leaves at maximum depth. If they are not siblings, exchange arguments rearrange leaves so that they become siblings without increasing cost. Combining them into a single symbol of frequency equal to their sum reduces the problem to a smaller instance. Induction then proves optimality.

Huffman coding assumes symbol frequencies are known or estimated and that a static or block code is appropriate. It may be less effective than arithmetic or context-based coding when symbol dependencies are strong.

7. Dijkstra’s Shortest-Path Algorithm

Given a directed or undirected graph with edge lengths w(u,v) ≥ 0, Dijkstra’s algorithm computes shortest distances from a source s. The distance of a path is the sum of its edge weights:

The algorithm maintains tentative distances d[v], initializes d[s] = 0 and all others to infinity, and repeatedly finalizes the unsettled vertex with minimum d[v]. It then relaxes outgoing edges:

if d[v] > d[u] + w(u,v)
    d[v] ← d[u] + w(u,v)
    predecessor[v] ← u

With a binary heap and adjacency lists, the complexity is O((|V| + |E|) log |V|), often written O(|E| log |V|) for connected graphs. With a Fibonacci heap, the theoretical bound is O(|E| + |V| log |V|), but implementation complexity and constants matter.

The invariant is that when the minimum tentative vertex u is selected, d[u] is final. If a shorter path existed, consider the first vertex on that path not yet finalized. Its predecessor on the path would already have been finalized and would have relaxed it to a value no greater than the alleged shorter path, contradicting u’s minimum tentative distance. Nonnegative edge weights are essential: a negative edge could reduce a supposedly finalized distance later.

Dijkstra is unsuitable for graphs with negative edges. Bellman–Ford handles negative edges and can detect reachable negative cycles, at a higher worst-case cost of O(|V||E|).

8. Greedy Algorithms in AI and ML Systems

Greedy design appears in AI engineering, although the underlying optimization problem must be identified carefully.

• Decision-tree induction greedily selects a split using criteria such as information gain or Gini reduction. The resulting tree is not guaranteed to be globally optimal; pruning and ensemble methods address overfitting.
• Beam search retains only the best k partial sequences at each level. It is a controlled approximation because a discarded partial sequence cannot be recovered.
• Feature selection may add the feature with the largest immediate validation improvement. Correlated features and interaction effects can make this myopic.
• Scheduling GPU jobs, model-serving requests, or data-processing tasks may use earliest-deadline or highest-priority rules. Such rules must be evaluated against fairness, starvation, and tail-latency objectives.
• Approximation algorithms for submodular maximization often use marginal gain per unit cost. Under suitable monotonicity and diminishing-returns assumptions, formal approximation guarantees can be obtained.

A greedy criterion may optimize a proxy rather than the true organizational objective. For example, choosing training examples only by immediate uncertainty may underrepresent minority regions of the data distribution. The selection rule should therefore be accompanied by validation, monitoring, and explicit constraints.

9. Applied Case: Scheduling Shared GPU Resources

Background

Consider an illustrative university AI laboratory with one GPU server. Researchers submit training jobs, each with a release time, expected completion time, deadline, and priority. The server cannot run two jobs simultaneously.

Problem

The laboratory wants high utilization and timely completion, but also wants to avoid indefinite postponement of low-priority projects. A naive rule that always selects the shortest job may improve average completion time while causing a long job to miss its deadline. A rule that always selects the highest priority may underutilize the server when a high-priority job is not yet ready.

Analysis

This is not automatically the classical interval-scheduling problem. Jobs may arrive dynamically, have different weights, and generate penalties for lateness. The objective could be maximum throughput, minimum total completion time, weighted tardiness, or a multi-objective combination. Each objective changes the mathematical problem and the correctness claims.

Approach

The laboratory uses a two-stage policy:

1. Reserve a protected capacity share for deadline-critical jobs.
2. Within the remaining eligible jobs, use shortest estimated processing time, with aging that increases the priority of waiting jobs.

The system records estimates, actual runtimes, queue delays, deadline misses, and resource utilization. A periodic review tests whether the heuristic improves the stated objectives without creating systematic disadvantage for particular research groups.

Outcome

The policy is operationally effective as a heuristic, but it is not claimed to be globally optimal. Its value comes from explicitly defining constraints, measuring trade-offs, and revising the rule when workload conditions change.

Learning points

First, the greedy rule must match the objective. Second, dynamic arrivals can invalidate a proof for a static problem. Third, estimates are uncertain, so robustness and monitoring matter. Finally, fairness constraints may be as important as throughput in shared institutional infrastructure.

10. Limitations, Failure Modes, and Best Practices

Greedy algorithms can fail because the local criterion ignores future interactions, because feasibility is nonlocal, or because the objective is not decomposable. Common warning signs include:

• a choice consumes a scarce resource needed by many later choices;
• items cannot be divided, as in 0–1 knapsack;
• negative edge weights invalidate shortest-path finalization;
• constraints involve global combinations rather than independent feasibility checks;
• the algorithm has no exchange, cut, or invariant proof;
• input estimates are noisy or the environment changes during execution.

Best practice is to construct small counterexamples before implementation, compare against an exact solver on small instances, state all assumptions, test ties and boundary cases, and report approximation guarantees when exact optimality is unavailable. Tie-breaking should be deterministic where reproducibility matters, but alternative tie-breaks should be tested where fairness or stability is important.

In deployed AI systems, governance requires documenting the objective function, protected constraints, data used to estimate costs or probabilities, and the consequences of errors. A greedy system that allocates opportunities, moderates content, or prioritizes public services should be audited for disparate impact and feedback loops. Efficiency does not justify opaque or discriminatory allocation.

Contemporary Developments

Modern greedy research increasingly combines exact structural reasoning with learned components. A model may predict which candidate is promising, while a feasibility checker preserves hard constraints. Learning-augmented algorithms use predictions to improve practical performance while retaining worst-case safeguards. Submodular optimization, online algorithms, matroid constraints, and primal-dual methods provide broader theoretical frameworks for greedy selection.

Online greedy algorithms face decisions without knowledge of future input. Their evaluation may use competitive analysis: an online algorithm is c-competitive for a maximization problem if its value is at least 1/c of the offline optimum, up to an additive constant, on every input sequence. This is distinct from ordinary worst-case approximation because the information available differs.

Chapter Summary

Greedy algorithms build solutions through locally preferred, usually irreversible choices. Their success depends on more than an attractive heuristic: a greedy-choice property and appropriate optimal-substructure argument must justify global optimality. Exchange arguments, staying-ahead proofs, invariants, and graph cut properties are central proof tools.

Earliest-finish-time selection solves maximum-cardinality interval scheduling. Value-to-weight ordering solves fractional knapsack but not 0–1 knapsack. Kruskal’s and Prim’s algorithms find minimum spanning trees through safe light-edge choices. Huffman coding repeatedly combines the two least-frequent symbols to obtain an optimal prefix code. Dijkstra’s algorithm uses a greedy finalization rule for nonnegative edge weights.

In AI and ML systems, greedy rules occur in search, feature selection, scheduling, and resource allocation. They may be exact, approximate, or merely heuristic. Sound design therefore requires precise objectives, explicit assumptions, complexity analysis, counterexample testing, empirical validation, and attention to fairness and governance.

Key Terms

Greedy algorithm: An algorithm that makes locally preferred choices while constructing a solution.

Greedy-choice property: The existence of an optimal solution beginning with the greedy choice.

Optimal substructure: The property that optimal solutions contain optimal solutions to residual subproblems.

Exchange argument: A proof that replaces a choice in an optimal solution with the greedy choice without worsening the objective.

Invariant: A statement preserved throughout algorithm execution.

Feasibility test: A procedure determining whether a candidate can be added without violating constraints.

Interval scheduling: Selecting the largest set of mutually compatible activities.

Fractional knapsack: Knapsack optimization in which item fractions are allowed.

Value-to-weight ratio: Item value divided by item weight.

Minimum spanning tree: A minimum-weight tree connecting every vertex of a connected undirected graph.

Cut property: A light edge crossing a suitable cut is safe for an MST.

Cycle property: Cycle structure can identify edges that may be excluded from an MST.

Disjoint-set union: A data structure supporting dynamic component membership and merging.

Prefix code: A code in which no codeword is a prefix of another.

Huffman coding: A greedy method for constructing an optimal binary prefix code.

Relaxation: Updating a tentative shortest-path distance when a better path is found.

Dijkstra’s algorithm: A shortest-path algorithm valid for nonnegative edge weights.

Approximation algorithm: An algorithm with a provable or empirically assessed relationship to an optimum.

Competitive analysis: Evaluation of an online algorithm relative to an offline optimum.

Review Questions

Short Answer Questions

1. Define the greedy-choice property and explain how it differs from optimal substructure.
2. Why does earliest finish time provide the correct greedy rule for maximum-cardinality interval scheduling?
3. State the condition on edge weights required by Dijkstra’s algorithm.
4. Why does the value-to-weight rule work for fractional knapsack but fail in general for 0–1 knapsack?
5. What role does a disjoint-set union structure play in Kruskal’s algorithm?

Long Answer Questions

1. Present and prove the interval-scheduling algorithm using an exchange or staying-ahead argument. Include its time complexity.
2. Explain Kruskal’s and Prim’s algorithms, compare their data structures and complexity, and relate both to the cut property.
3. Describe Huffman coding, work through its repeated-combination process, and justify its optimality.
4. Explain Dijkstra’s invariant and provide a counterexample showing why negative edge weights invalidate the algorithm.
5. Compare greedy algorithms with dynamic programming, using fractional knapsack and 0–1 knapsack as a central example.

Analytical / Application Questions

1. Design a greedy policy for allocating shared GPU jobs. State the objective, feasibility constraints, assumptions, metrics, and circumstances under which the policy could fail.
2. Construct a small 0–1 knapsack instance for which value-to-weight ordering is suboptimal. Verify the greedy and optimal values.
3. A feature-selection system chooses the feature with the largest immediate validation improvement. Analyse two risks caused by correlated features or distribution shift, and propose safeguards.

Multiple Choice Questions with Answers

Question 1

Which property specifically justifies making an irrevocable local choice in a greedy algorithm?

A. Greedy-choice property

B. Overlapping subproblems

C. Random access property

D. Hashing property

Correct Answer: A. Greedy-choice property

Question 2

For maximum-cardinality interval scheduling, which activity should be selected first?

A. The activity with the earliest start time

B. The activity with the shortest duration

C. The activity with the earliest finish time

D. The activity with the largest number of conflicts

Correct Answer: C. The activity with the earliest finish time

Question 3

In fractional knapsack, an item with value 80 and weight 20 has which value-to-weight ratio?

A. 0.25

B. 4

C. 20

D. 100

Correct Answer: B. 4

Question 4

Why is value-to-weight ordering not generally optimal for 0–1 knapsack?

A. Items cannot have values

B. Fractions are mandatory

C. An item must be taken whole or not taken, creating combinations the ratio ignores

D. The capacity is always unlimited

Correct Answer: C. An item must be taken whole or not taken, creating combinations the ratio ignores

Question 5

What condition does Kruskal’s algorithm check before adding an edge?

A. Whether the edge has maximum weight

B. Whether the edge connects two different components

C. Whether the edge points toward the source

D. Whether the edge has negative weight

Correct Answer: B. Whether the edge connects two different components

Question 6

What does Huffman’s algorithm repeatedly combine?

A. The two most frequent symbols

B. The two least frequent nodes

C. The longest codewords

D. Two arbitrary subtrees

Correct Answer: B. The two least frequent nodes

Question 7

Dijkstra’s algorithm is guaranteed correct when:

A. All edge weights are nonnegative

B. All edge weights are negative

C. The graph is necessarily complete

D. There is exactly one path between every pair of vertices

Correct Answer: A. All edge weights are nonnegative

Question 8

Using a binary heap and adjacency lists, a standard complexity bound for Dijkstra’s algorithm is:

A. O(1)

B. O(|V|²) for every graph

C. O((|V| + |E|) log |V|)

D. O(2^{|V|})

Correct Answer: C. O((|V| + |E|) log |V|)

Question 9

Which proof technique replaces a choice in an optimal solution with the greedy choice while preserving feasibility and value?

A. Exchange argument

B. Backtracking tree

C. Hash collision proof

D. Dimensional analysis

Correct Answer: A. Exchange argument

Question 10

For frequencies 5, 9, 12, 13, 16, and 45, what is the first pair combined by Huffman coding?

A. 5 and 9

B. 9 and 12

C. 13 and 16

D. 16 and 45

Correct Answer: A. 5 and 9