5. Greedy Algorithm Design

Introduction and Context

Greedy algorithms provide one of the most elegant ways to solve optimization problems. At each stage, a greedy method makes the locally best decision available, with the expectation that a sequence of such decisions will produce a globally optimal solution. This strategy is attractive because it is usually simple to describe, efficient to implement, and often substantially faster than exhaustive search or dynamic programming.

The central difficulty is that local optimality does not generally imply global optimality. A decision that appears best at one moment may prevent a better combination later. Consequently, greedy algorithm design is not merely a matter of choosing the largest, smallest, earliest, or cheapest available item. It requires a proof that the selection rule is safe. In postgraduate algorithm study, the essential skill is therefore not only constructing a greedy algorithm, but also establishing its correctness through an exchange argument, a cut property, a dominance argument, or a matroid formulation.

Greedy methods are fundamental in scheduling, network design, data compression, resource allocation, graph optimization, and approximation systems. Algorithms such as activity selection, Huffman coding, Kruskal’s minimum spanning tree algorithm, Prim’s algorithm, and Dijkstra’s shortest-path algorithm illustrate both the power and the boundaries of the paradigm.

Learning Objectives

After completing this chapter, the reader should be able to:

• explain the greedy-choice property and optimal substructure;
• distinguish problems that admit greedy solutions from those requiring dynamic programming or other techniques;
• design greedy algorithms for scheduling, coding, resource allocation, and spanning-tree problems;
• prove correctness using exchange arguments, cut and cycle properties, and matroid concepts;
• analyze time and space complexity, including the cost of sorting and priority-queue operations;
• identify failure cases, implementation risks, and inappropriate applications of greedy methods;
• evaluate the role of greedy algorithms in modern software and AI/ML systems.

The Greedy Paradigm

A greedy algorithm constructs a solution incrementally. At every iteration it selects a feasible candidate according to a local criterion, commits to that choice, and never revisits it. A general scheme is:

1. Define the set of candidates.

2. Identify the feasibility condition.

3. Select the most promising remaining candidate.

4. Add it if feasibility is preserved.

5. Repeat until a complete solution is obtained.

Three sets are useful for reasoning about this process: the candidates not yet considered, the partial solution already selected, and the candidates that remain feasible. A priority queue is often used to identify the next candidate efficiently, while sorting is frequently performed once at the beginning.

Two properties usually underlie a successful greedy solution.

Greedy-choice property

A problem has the greedy-choice property when there exists an optimal solution beginning with the choice made by the greedy rule. This does not mean that every optimal solution begins with that choice; it means that at least one can be transformed so that it does.

Optimal substructure

A problem has optimal substructure when, after a safe choice is made, the remaining decisions form a smaller problem whose optimal solution can be combined with the initial choice to form an optimal solution to the original problem.

Optimal substructure alone is insufficient. Many dynamic programming problems have it, but their first choice cannot be fixed safely without considering future consequences. Greedy design requires both a safe local choice and a suitably reduced residual problem.

Proving Greedy Correctness

Exchange arguments

An exchange argument begins with an arbitrary optimal solution and modifies it so that its first decision agrees with the greedy decision, without making the solution worse. The modified solution remains optimal. The argument is then repeated, explicitly or inductively, for the remaining problem.

For example, in interval scheduling, suppose activities are ordered by increasing finishing time. Let the greedy activity be the one finishing earliest, and let an optimal schedule begin with another activity. Replacing that first activity with the greedy activity cannot reduce the number of activities that can subsequently be selected, because the greedy activity finishes no later. Thus an optimal schedule exists that begins greedily.

Cut properties

A cut divides the vertices of a graph into two disjoint sets. An edge crossing the cut has one endpoint on each side. In a connected weighted graph, a light edge crossing a cut is safe for a minimum spanning tree when the cut respects the edges already selected. This cut property justifies both Kruskal’s and Prim’s algorithms.

The statement must be used carefully. An arbitrary light edge is not always safe if previously selected edges create inappropriate constraints. In standard minimum spanning tree proofs, the selected edges form a forest, and the cut is chosen so that no selected edge crosses it.

Cycle properties

For a cycle in a weighted graph, a heaviest edge can be excluded from at least one minimum spanning tree, provided it is uniquely heaviest; more generally, there exists a minimum spanning tree avoiding a maximum-weight edge on the cycle. This property explains why Kruskal’s algorithm rejects an edge that would create a cycle.

Matroid perspective

Matroids provide an abstract framework for understanding why many greedy algorithms work. A matroid consists of a finite ground set and a family of independent subsets satisfying:

• the empty set is independent;
• every subset of an independent set is independent;
• if one independent set is smaller than another, an element from the larger can be added to the smaller while preserving independence.

For a weighted matroid, repeatedly selecting the highest-weight feasible element produces a maximum-weight independent set. The exchange axiom is the mathematical reason that locally best feasible choices can be globally optimal. Graphic matroids, whose independent sets are forests of a graph, provide the theoretical foundation for minimum spanning tree algorithms.

Not every optimization problem is a matroid problem. Recognizing this limitation prevents the unjustified use of greedy rules.

Scheduling: Selecting the Maximum Number of Activities

Consider a set of activities, each with a start time and finish time. The objective is to select the largest possible subset of mutually compatible activities, where compatible activities do not overlap.

The correct greedy rule is to select the feasible activity with the earliest finish time. A procedure is:

```text

sort activities by nondecreasing finish time

lastFinish = -infinity

for each activity (s, f):

if s >= lastFinish:

select the activity

lastFinish = f

```

With sorting, the running time is O(n log n), and the scan is O(n). If the activities are already sorted, the running time is O(n).

The proof follows an exchange argument. Let a be the activity with the earliest finish time and let O be an optimal solution. If O already begins with a, there is nothing to prove. Otherwise, let b be the first activity in O. Since a finishes no later than b, replacing b with a leaves every later activity in O compatible. Therefore an optimal solution begins with a. The remaining activities begin after a finishes and constitute a smaller instance. Induction proves optimality.

A common mistake is to select the shortest activity, the activity with the earliest start, or the activity that overlaps the fewest others. These rules may fail because they do not maximize the space available for all subsequent selections.

The problem changes substantially when activities have weights or profits. Selecting the maximum number is no longer the same as maximizing total value. Weighted interval scheduling is generally solved by dynamic programming, not by the earliest-finish greedy rule.

Fractional Resource Allocation

In the fractional knapsack problem, item i has value vi and weight wi, and fractions of an item may be taken. The capacity is W. The appropriate greedy criterion is value density vi/wi. Items are considered in decreasing order of density, and as much as possible is taken from each item.

The exchange proof is direct. Suppose a feasible solution contains a positive amount of an item with lower density while some amount of a higher-density item remains available. Replacing a small quantity of the lower-density item with the same weight of the higher-density item increases total value. Therefore an optimal solution cannot have this pattern, and all higher-density material must be exhausted before lower-density material is used.

The algorithm runs in O(n log n) because of sorting. This result depends critically on divisibility. In the 0–1 knapsack problem, an item must be taken whole or rejected. Density ordering can be arbitrarily poor there, and dynamic programming or approximation techniques are more appropriate.

This distinction is important in resource allocation. Divisible bandwidth, liquid commodities, and continuously allocated processing capacity may support greedy density rules. indivisible projects, machines, or contracts usually do not.

Huffman Coding and Greedy Compression

Huffman coding constructs a prefix-free binary code that minimizes the weighted average code length for a set of symbols. If symbol i occurs with frequency fi, the objective is to minimize the sum of fi multiplied by its codeword length.

The algorithm repeatedly combines the two least frequent nodes. Their combined frequency becomes the frequency of a new internal node, which is inserted back into a priority queue. The process ends when one tree remains. The two child edges may be labeled 0 and 1.

A key lemma states that in some optimal prefix code, the two least frequent symbols are siblings at the greatest depth. Intuitively, placing low-frequency symbols deeper causes less contribution to the weighted path length. If they are not siblings in an optimal tree, exchanging tree positions can move them to the deepest sibling positions without increasing cost. Combining the two symbols into one pseudo-symbol reduces the problem to a smaller instance. This establishes optimality by induction.

With a binary heap, Huffman construction takes O(n log n). The resulting code is prefix-free, so encoded messages can be decoded without separators. In practice, the encoder and decoder must also agree on the code tree or a canonical representation of it.

Huffman coding illustrates that greedy algorithms can construct not merely a numerical solution but a complete data structure. It remains useful in compression systems, although modern formats may combine it with dictionary coding, arithmetic coding, or context modeling.

Minimum Spanning Trees

Given a connected, undirected, weighted graph G = (V, E), a minimum spanning tree is a spanning tree with minimum total edge weight. A tree contains all vertices, has no cycle, and contains |V| − 1 edges.

Kruskal’s algorithm

Kruskal’s algorithm sorts edges in nondecreasing order of weight and adds an edge whenever it does not form a cycle with the selected edges. A disjoint-set union structure supports efficient cycle detection.

```text

sort edges by nondecreasing weight

make each vertex a separate set

for each edge (u, v) in sorted order:

if Find(u) != Find(v):

add (u, v) to the tree

Union(u, v)

```

Sorting costs O(E log E). With union by rank and path compression, the disjoint-set operations are almost constant amortized time, giving an overall complexity commonly written as O(E log E).

The proof uses the cut property. At any stage, the selected edges form a forest. If an edge connects two different components, choose the cut consisting of one component and the rest of the graph. The chosen edge is a light edge crossing that cut among the edges considered that can connect the components. It is safe to add it. Kruskal’s algorithm stops after |V| − 1 safe additions.

Prim’s algorithm

Prim’s algorithm grows one tree from an initial vertex. At each step, it selects the minimum-weight edge connecting the current tree to a vertex outside it. With a binary heap and adjacency lists, the complexity is O(E log V); with a dense adjacency matrix, O(V²) may be preferable.

The cut property proves correctness. The current tree defines a cut between included and excluded vertices. The minimum crossing edge is safe, so each extension preserves the possibility of completing a minimum spanning tree.

Kruskal is often convenient for edge-oriented or sparse data, whereas Prim naturally fits a vertex-expansion view and can be efficient for dense graphs. If edge weights are equal, multiple minimum spanning trees may exist, but both algorithms still produce one of them.

Dijkstra’s Algorithm: A Boundary of Greedy Reasoning

Dijkstra’s algorithm solves the single-source shortest-path problem when all edge weights are nonnegative. It repeatedly finalizes the unprocessed vertex with the smallest tentative distance and relaxes its outgoing edges.

The greedy choice is safe because, with nonnegative edge weights, any route to an unprocessed vertex through another unprocessed vertex cannot produce a shorter distance than the smallest tentative distance already selected. A priority-queue implementation runs in O((V + E) log V) with suitable graph representations.

Negative edges invalidate the proof. A vertex finalized early may later be reached by a shorter path through a negative edge. Bellman–Ford is required when negative edge weights are possible. This example demonstrates that a familiar greedy algorithm is valid only under explicit assumptions.

A Case Study: Designing a Campus Network

Background

Consider an illustrative university campus with six buildings connected by possible fiber links. Each link has an installation cost. The network team must connect all buildings at minimum total cost while avoiding unnecessary redundant links.

Situation and analysis

The possible links are: A–B (4), A–C (2), B–C (1), B–D (5), C–D (8), C–E (10), D–E (2), D–F (6), E–F (3), and B–F (9). The requirement is connectivity, not resilience; therefore a spanning tree is appropriate.

Kruskal’s algorithm sorts the links as B–C (1), A–C (2), D–E (2), E–F (3), A–B (4), B–D (5), D–F (6), C–D (8), B–F (9), and C–E (10). It selects B–C, A–C, D–E, E–F, and B–D. The next edge D–F would form a cycle through D–E–F, so it is rejected. The selected five edges connect all six buildings, with total cost 13.

Strategy and solution

The network team uses a disjoint-set structure to maintain connected components. Each accepted edge is justified by the cut property; each rejected edge is unnecessary for a minimum spanning tree because it closes a cycle.

Outcome

The resulting installation connects every building at minimum cost under the stated model. If the university later requires fault tolerance, bandwidth guarantees, or latency constraints, the problem changes. A minimum spanning tree alone may no longer be an adequate design.

Learning points

The case illustrates the importance of matching the objective to the algorithm. Greedy optimization is correct for minimum total connection cost, but practical network engineering may require multi-objective optimization, survivable network design, or integer programming.

Limitations, Risks, and Common Errors

The most serious error is assuming that a plausible local rule is automatically valid. A greedy algorithm should be accompanied by a proof or by a clearly stated approximation guarantee. Other frequent errors include:

• ignoring whether items are divisible;
• applying an unweighted scheduling rule to weighted activities;
• using Dijkstra’s algorithm with negative edges;
• confusing a minimum spanning tree with a shortest-path tree;
• overlooking disconnected graphs in minimum spanning tree implementations;
• mishandling ties when a proof depends on a particular ordering;
• using floating-point comparisons carelessly in density-based allocation;
• failing to preserve invariants in priority queues or disjoint-set structures.

Greedy algorithms can also be unsuitable when decisions are reversible only at high cost, when future information is unavailable, or when the objective contains complex interactions. In online environments, a greedy rule may be competitive without being optimal; its quality should then be expressed through a competitive ratio or approximation bound.

Professional and Technological Applications

Greedy methods occur in compilers, operating systems, communication networks, databases, logistics, and machine learning pipelines. Priority-based scheduling, feature selection heuristics, clustering initialization, bandwidth allocation, and graph construction frequently use greedy subroutines.

In AI and ML, greedy search may select the next best split in a decision tree, choose actions in a heuristic planner, or build a sparse structure incrementally. Such choices can improve computational speed but may introduce bias or local optima. A system should distinguish an exact greedy algorithm, whose assumptions support a proof of optimality, from a heuristic that merely performs well empirically.

Automation also raises governance concerns. A resource-allocation rule that greedily maximizes throughput may systematically disadvantage a group if fairness constraints are omitted. In production systems, objectives, constraints, tie-breaking rules, logging, and monitoring should be explicit. When decisions affect people, explainability and auditability are important, even when the underlying algorithm is mathematically simple.

Current Directions and Best Practices

Contemporary algorithm engineering combines greedy strategies with other methods. A greedy construction may provide an initial solution for local search, branch-and-bound, integer programming, or evolutionary optimization. Streaming and distributed systems use one-pass greedy summaries when storing all data is impossible, often with approximation guarantees.

Effective practice includes:

1. State the objective and feasibility constraints precisely.

2. Test the proposed rule against small counterexamples before attempting a proof.

3. Identify the invariant preserved after each selection.

4. Prove the greedy choice using exchange, cut, or dominance reasoning.

5. Analyze the cost of sorting, heaps, graph representation, and auxiliary structures.

6. Document assumptions such as nonnegative weights, divisibility, or independence.

7. Separate exact algorithms from heuristics and report quality guarantees where available.

8. Test ties, empty inputs, disconnected graphs, duplicate values, and extreme numeric ranges.

Chapter Summary

Greedy algorithms build solutions by repeatedly making a locally best feasible choice. Their success depends on more than intuition: the problem must support a safe greedy choice and an appropriate optimal-substructure argument. Exchange arguments establish the correctness of activity selection, fractional knapsack, and Huffman coding. Cut and cycle properties justify minimum spanning tree algorithms such as Kruskal’s and Prim’s. Matroids provide a general mathematical explanation for greedy optimization over independence systems.

Greedy methods are efficient and widely applicable, but their assumptions are decisive. Weighted scheduling, 0–1 knapsack, negative-edge shortest paths, and multi-objective network design demonstrate situations where a simple greedy rule fails or requires modification. Sound algorithm design therefore combines construction, proof, complexity analysis, testing, and awareness of professional constraints.

Key Terms

Greedy algorithm: An algorithm that repeatedly commits to a locally preferred feasible choice.

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 suitable subproblems.

Exchange argument: A proof that transforms an optimal solution to include a greedy choice without worsening it.

Feasible solution: A solution satisfying all problem constraints.

Activity selection: Choosing the maximum number of mutually compatible intervals.

Fractional knapsack: A resource-allocation problem in which item quantities may be divided.

Value density: Value per unit of weight or resource.

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

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

Spanning tree: A cycle-free connected subgraph containing every vertex.

Minimum spanning tree: A spanning tree of minimum total edge weight.

Cut property: The principle that a suitable light edge crossing a cut is safe for an MST.

Cycle property: The principle that an appropriate heaviest cycle edge can be excluded from an MST.

Disjoint-set union: A data structure supporting efficient set merging and membership queries.

Matroid: An independence system satisfying hereditary and exchange axioms.

Relaxation: The operation of replacing a tentative shortest-path distance with a smaller value.

Approximation guarantee: A formal bound on the quality of a nonoptimal algorithmic solution.

Greedy heuristic: A locally directed method without a general proof of exact optimality.

Review Questions

Short Answer Questions

1. What is the greedy-choice property?

2. Why does optimal substructure alone not guarantee a greedy solution?

3. State the greedy rule for unweighted activity selection.

4. Why is a disjoint-set structure useful in Kruskal’s algorithm?

5. What restriction on edge weights is required by Dijkstra’s algorithm?

Long Answer Questions

1. Explain the exchange-argument proof for the activity-selection algorithm.

2. Describe Huffman coding and prove why combining the two least frequent symbols is safe.

3. Compare Kruskal’s and Prim’s algorithms in terms of strategy, data structures, and complexity.

4. Explain the cut and cycle properties of minimum spanning trees and their relationship to greedy correctness.

5. Discuss how matroid theory generalizes the conditions under which greedy algorithms are optimal.

Analytical / Application Questions

1. Given activities (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), and (8,11), apply earliest-finish scheduling and justify the result.

2. Construct a counterexample showing that sorting 0–1 knapsack items by value density does not always produce an optimal solution.

3. For a weighted graph of your choice, execute Kruskal’s algorithm, identify every rejected cycle-forming edge, and prove that the final tree is minimum.

22. Multiple Choice Questions with Answers

Question 1

Which condition is essential for proving that a greedy choice is safe?

A. Every candidate must have the same weight

B. Some optimal solution can be transformed to include the greedy choice

C. The problem must contain overlapping subproblems

D. The input must already be sorted

Correct Answer: B. Some optimal solution can be transformed to include the greedy choice

Question 2

For unweighted activity selection, which activity should be selected first?

A. The one with the earliest start time

B. The shortest-duration activity

C. The one with the earliest finish time

D. The activity overlapping the fewest others

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

Question 3

Why does value density give an optimal rule for fractional knapsack?

A. Items are always selected whole

B. A lower-density portion can be exchanged for a higher-density portion

C. The capacity is unlimited

D. All item values are equal

Correct Answer: B. A lower-density portion can be exchanged for a higher-density portion

Question 4

What does Huffman’s algorithm repeatedly combine?

A. The two most frequent symbols

B. The two symbols with equal code lengths

C. The two least frequent nodes

D. The two longest codewords

Correct Answer: C. The two least frequent nodes

Question 5

In Kruskal’s algorithm, an edge is rejected when it:

A. Has a positive weight

B. Connects two different components

C. Creates a cycle among selected edges

D. Is considered after the first edge

Correct Answer: C. Creates a cycle among selected edges

Question 6

Which property directly justifies adding a suitable light edge across a cut in an MST algorithm?

A. Optimal substructure property

B. Cut property

C. Prefix property

D. Relaxation property

Correct Answer: B. Cut property

Question 7

What is the principal role of disjoint-set union in Kruskal’s algorithm?

A. Sorting vertices by degree

B. Detecting whether an edge joins vertices already connected

C. Computing shortest paths

D. Encoding edge weights

Correct Answer: B. Detecting whether an edge joins vertices already connected

Question 8

Why can Dijkstra’s algorithm fail when negative edge weights are present?

A. It cannot store negative numbers

B. A finalized vertex may later receive a shorter path

C. The graph necessarily becomes disconnected

D. Priority queues cannot contain zero values

Correct Answer: B. A finalized vertex may later receive a shorter path

Question 9

Which problem generally cannot be solved optimally by simply sorting items by value density?

A. Fractional knapsack

B. Unweighted activity selection

C. 0–1 knapsack

D. Huffman coding

Correct Answer: C. 0–1 knapsack

Question 10

In the matroid framework, which axiom enables exchange-based greedy reasoning?

A. Every set must contain all elements

B. Independent sets must have equal size

C. An element from a larger independent set can extend a smaller one

D. Weights must be negative

Correct Answer: C. An element from a larger independent set can extend a smaller one