Greedy Algorithms and Matroid Foundations

Introduction

A greedy algorithm constructs a solution incrementally. At each step it selects the locally best available option according to a specified rule, permanently commits to that choice, and continues until a complete solution is obtained. Greedy methods are attractive because they are often simple, fast, and memory-efficient. Their apparent simplicity, however, can be misleading: local optimality does not generally imply global optimality.

The central intellectual task in greedy algorithm design is therefore not merely identifying a plausible selection rule. It is proving that the rule is safe. This chapter develops the principal proof techniques—exchange arguments, cut properties, and matroid theory—that explain when greedy selection succeeds and when it fails.

Greedy algorithms are fundamental in network optimization, scheduling, compression, approximation, machine learning pipelines, resource allocation, and distributed systems. In AI and ML, they appear in feature selection, decision-tree construction, matching heuristics, prototype selection, and submodular optimization.

Learning Objectives

After studying this chapter, you should be able to:

• characterize the structure of a greedy algorithm;
• distinguish feasibility, optimality, and approximation guarantees;
• prove greedy correctness using exchange arguments and cut properties;
• apply greedy algorithms to activity selection, fractional knapsack, Huffman coding, and minimum spanning trees;
• explain the role of matroids and the greedy theorem;
• identify counterexamples showing why greedy selection fails;
• analyze time complexity and implementation choices; and
• evaluate greedy methods in AI/ML applications.

1. The Greedy Design Paradigm

Let a problem have a set of candidate elements and a feasible solution family. A greedy algorithm repeatedly performs four actions:

1. rank or otherwise evaluate currently available candidates;
2. select the best candidate according to a local rule;
3. accept it if feasibility is preserved; and
4. never reconsider the decision.

A generic schema is:

S ← ∅
while candidates remain:
    x ← best remaining candidate according to the rule
    remove x from consideration
    if S ∪ {x} is feasible:
        S ← S ∪ {x}
return S

The word “best” is problem-specific. It may mean earliest finishing time, largest value-to-weight ratio, smallest edge weight, or smallest frequency. The selection rule must be stated precisely; vague claims such as “choose the most useful item” are not algorithmic specifications.

Three properties must be separated:

• Feasibility: the constructed set satisfies all constraints.
• Optimality: no feasible solution has a better objective value.
• Approximation quality: the solution has a provable relationship to the optimum but may not equal it.

A greedy algorithm may always preserve feasibility while producing poor solutions. Correctness consequently requires both a feasibility argument and an optimality proof.

2. Conditions Supporting Greedy Choice

Two structural ideas commonly justify greedy algorithms.

2.1 Greedy-choice property

A problem has the greedy-choice property when at least one optimal solution begins with, or contains, the choice made by the algorithm. This does not mean that every locally best choice appears in every optimum. It means that the chosen option can be extended to an optimum.

2.2 Optimal substructure

A problem has optimal substructure when, after making a correct choice, the remaining part of an optimal solution is itself optimal for the residual problem. If a residual solution could be improved, replacing it would improve the original solution, contradicting optimality.

Optimal substructure alone is insufficient. Many dynamic-programming problems have it but lack a safe greedy choice. For example, shortest paths with arbitrary nonnegative edge weights have optimal substructure, but a single local rule such as choosing the smallest outgoing edge does not solve the problem.

2.3 A proof template

A robust greedy proof often follows this pattern:

1. Let G be the solution produced by the algorithm and O an arbitrary optimal solution.
2. Show that the greedy first choice can replace a corresponding choice in O without decreasing quality.
3. Conclude that there exists an optimal solution containing the greedy choice.
4. Apply the same reasoning to the residual problem.
5. Establish termination and feasibility.

This replacement step is the exchange argument.

3. Exchange Arguments

An exchange argument transforms an optimal solution into one that agrees with the greedy algorithm. The transformation must preserve feasibility and must not worsen the objective.

3.1 Activity-selection problem

Given activities i with start time sᵢ and finish time fᵢ, select the largest subset of mutually compatible activities. Two activities are compatible when one finishes no later than the other starts.

The greedy rule is: select the compatible activity with the earliest finish time.

#### Theorem

Earliest-finish-time selection produces a maximum-cardinality compatible activity set.

#### Proof

Let g be the activity with minimum finish time. Consider an optimal solution O whose first selected activity is o. Since f_g ≤ f_o, replace o with g. Any activity compatible with o and selected after o starts at or after f_o, and therefore also starts at or after f_g. The replacement remains feasible and does not change the number of activities. Thus some optimal solution begins with g.

After selecting g, the remaining task is the same problem restricted to activities with sᵢ ≥ f_g. Applying the argument recursively proves optimality. ∎

#### Worked example

Suppose activities are:

Sort by finish time: A, B, C, D, E, F, G, H, I, J, K. Select A (1–4), then D (5–7), then H (8–11), then K (12–16). The result contains four activities. The exchange proof, rather than the numerical outcome alone, establishes that four is maximum.

4. Fractional Knapsack and the Boundary of Greedy Success

In the fractional knapsack problem, item i has value vᵢ and weight wᵢ, with wᵢ > 0. A capacity W is given, and fractions of items may be taken. The objective is to maximize total value subject to total weight at most W.

The greedy rule is to order items by value density:

where ρᵢ is value per unit weight. Take items in nonincreasing order of ρᵢ, taking a final fraction if necessary.

#### Exchange proof

Suppose a feasible solution contains some amount of item j while an available amount of item i has higher density, ρᵢ > ρⱼ. Replacing a small weight amount δ from j with the same weight amount of i changes value by δ(ρᵢ − ρⱼ) > 0. Therefore an optimum cannot allocate lower-density material while higher-density material remains available. The density ordering is optimal.

#### Example

Let capacity W = 50 and items be (value, weight): (60, 10), (100, 20), and (120, 30). Their densities are 6, 5, and 4. Take the first two items and 20 of the remaining 30 units of the third item. The value is:

The result is optimal for the fractional problem.

The same rule fails for 0/1 knapsack, where an item must be taken whole or rejected. For capacity 50 and items (60,10), (100,20), and (120,30), density greedy chooses the first two, value 160, whereas taking the second and third gives value 220. The indivisibility constraint destroys the exchange argument. Dynamic programming or branch-and-bound is required for exact general solutions.

5. Minimum Spanning Trees and Cut Properties

For a connected, undirected, weighted graph G = (V, E), a spanning tree connects every vertex using |V| − 1 edges and contains no cycle. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

5.1 Cut property

A cut partitions V into two nonempty sets S and V − S. An edge crosses the cut if one endpoint lies in each set. A light edge is a minimum-weight edge crossing that cut.

Cut property: If an edge is a unique light edge across a cut, it belongs to every MST. More generally, a light edge across a cut is safe: there exists an MST containing it.

#### Proof by exchange

Let e be a light crossing edge and let T be an MST not containing e. Adding e to T creates a cycle. That cycle contains another edge f crossing the same cut. Because e is light, w(e) ≤ w(f). Removing f yields a spanning tree T′ with weight no greater than T. Since T was minimum, T′ is also an MST and contains e. ∎

5.2 Kruskal’s algorithm

Kruskal’s algorithm sorts edges by nondecreasing weight and adds an edge when it does not create a cycle. A disjoint-set union structure efficiently tests whether two endpoints are already connected.

With sorting as the dominant operation, its complexity is O(|E| log |E|). Union-find operations contribute approximately O(|E| α(|V|)), where α is the inverse Ackermann function and grows extraordinarily slowly.

5.3 Prim’s algorithm

Prim’s algorithm starts from any vertex and repeatedly adds the minimum-weight edge connecting the current tree to an outside vertex. With a binary heap and adjacency lists, its complexity is O(|E| log |V|); with suitable representations, other bounds are possible.

Kruskal is often convenient for sparse edge lists and naturally builds a forest. Prim is often convenient for dense graphs or adjacency-based implementations. Both are justified by the cut property.

6. Huffman Coding

Huffman coding constructs an optimal prefix-free binary code for symbols with known frequencies. A prefix-free code ensures that no codeword is the prefix of another, allowing unambiguous decoding.

The greedy rule is to repeatedly merge the two least frequent trees. Their combined frequency becomes the frequency of a new internal node. A min-priority queue supports each extraction and insertion.

Greedy proof idea

In an optimal prefix code, two least frequent symbols can be placed as sibling leaves at maximum depth. If they are not siblings, exchanging their positions with two deepest siblings does not increase the weighted path length. Merging the sibling pair produces a smaller instance whose optimal solution can be expanded by assigning 0 and 1 to the two merged children. This establishes both the greedy choice and optimal substructure.

If symbol i has frequency pᵢ and code length ℓᵢ, the expected code length is:

where pᵢ ≥ 0 and ∑ᵢ pᵢ = 1. Huffman coding minimizes L among binary prefix-free codes for the given frequencies.

7. Matroid Foundations

Matroids provide an abstract framework explaining a large class of successful greedy algorithms.

A matroid is a pair M = (E, 𝓘), where E is a finite ground set and 𝓘 is a collection of independent subsets satisfying:

1. Nonemptiness: ∅ ∈ 𝓘.
2. Hereditary property: If A ∈ 𝓘 and B ⊆ A, then B ∈ 𝓘.
3. Exchange property: If A, B ∈ 𝓘 and |A| < |B|, then some x ∈ B − A satisfies A ∪ {x} ∈ 𝓘.

A maximal independent set is a basis. The exchange axiom implies that all bases have equal cardinality, called the rank of the matroid.

7.1 Graphic matroid

For a graph, E is the edge set and 𝓘 consists of acyclic edge sets. The independent sets are forests, and the bases are spanning trees when the graph is connected. Kruskal’s algorithm is therefore a weighted matroid greedy algorithm.

7.2 Partition matroid

Partition E into groups E₁, E₂, …, Eₖ and impose an upper bound bⱼ on selections from group Eⱼ. A set is independent if it selects at most bⱼ elements from each group. This models quotas, category constraints, and some resource-allocation problems.

7.3 Weighted matroid greedy theorem

Assign each element e a weight w(e). Sort elements in nonincreasing weight order and add an element whenever independence is preserved. For a matroid, this algorithm produces a maximum-weight independent set.

The theorem explains why greedy works for selecting a maximum-weight basis and why arbitrary independence systems do not receive the same guarantee. The exchange axiom permits one to transform an optimum so that it contains each greedy choice without reducing weight.

Matroid theory is a recognition tool. When feasibility is hereditary and has a strong exchange property, greedy design is promising. When adding one element can invalidate many unrelated structural possibilities, the matroid framework may not apply.

8. When Greedy Algorithms Fail

Greedy failure is not exceptional; it is a predictable consequence of missing exchange structure.

8.1 Coin change

For coin denominations 1, 3, and 4 and target 6, greedy selects 4, then 1, then 1, using three coins. The optimum is 3 + 3, using two. Canonical currency systems such as common decimal denominations often support greedy change-making, but arbitrary denominations do not.

8.2 Set cover

Given a universe of elements and subsets covering them, repeatedly choosing the set covering the largest number of uncovered elements is a heuristic, not an exact algorithm in general. The standard greedy algorithm has an approximation guarantee of 1 + ln n for a universe of n elements under the usual unweighted formulation, but exact optimization is NP-hard.

8.3 General knapsack

As shown earlier, density is decisive only when fractions are allowed. In 0/1 knapsack, indivisibility creates complementarities: choosing one item changes the value of other choices in a way that local density cannot capture.

8.4 Diagnostic questions

Before adopting greedy selection, ask:

• Can a locally best choice always be exchanged into some optimum?
• Does feasibility satisfy heredity and an exchange-like property?
• Does the objective decompose cleanly after the choice?
• Can a small counterexample defeat the proposed rule?
• Is an approximation guarantee acceptable if exactness fails?

Constructing small counterexamples is a professional skill. Test equal weights, extreme ratios, nested sets, and instances where an apparently attractive choice blocks several moderate choices.

9. Applied Case: Greedy Feature Selection in an AI Pipeline

Illustrative case. A fraud-detection team has thousands of candidate features and limited model-training time. It uses forward selection: begin with no features, add the feature producing the largest validation improvement, and stop when the improvement falls below a threshold.

Background and problem

The team needs a compact, interpretable model. Exhaustive search over all feature subsets is infeasible because the number of subsets grows exponentially with the number of features.

Analysis

Forward selection is greedy. Its choice is based on the current marginal validation gain. However, feature interactions mean that two individually weak features may jointly be powerful. Correlated features can also cause unstable selections, and repeated validation can overfit the holdout data.

Approach

The team uses nested cross-validation, records marginal gains, removes highly redundant features, and compares the greedy result with regularized models such as L₁-penalized regression and with a beam-search baseline. It reports not only predictive performance but also selection stability and computational cost.

Outcome

The greedy method produces a useful compact model quickly, but it is not claimed to be globally optimal. The final choice is made using an external test set and operational criteria such as latency, fairness, and interpretability.

Learning points

Greedy methods are valuable engineering compromises when search is expensive. In ML, validation design is part of algorithmic correctness: using the test set during selection invalidates the reported generalization estimate. Moreover, a local predictive gain must not override fairness, privacy, or causal considerations.

10. Implementation and Professional Practice

1. Make the rule deterministic. Specify tie-breaking, especially when reproducibility matters.
2. Sort once where possible. Sorting usually costs O(n log n); avoid repeated sorting.
3. Maintain feasibility efficiently. Use union-find for connectivity, heaps for repeated minimum extraction, and interval endpoints for scheduling.
4. Separate construction from proof. A correct implementation does not establish optimality.
5. Check numerical issues. Floating-point ratios may produce inconsistent orderings; cross-multiplication can sometimes avoid division when values are integers.
6. Test adversarial instances. Random tests are insufficient for exposing structural failures.
7. Report guarantees honestly. Distinguish exact optimality from approximation, heuristic performance, and empirical success.

11. Limitations, Ethics, and Contemporary Directions

Greedy algorithms can amplify short-term objectives. In resource allocation, a locally efficient decision may systematically exclude disadvantaged groups. In automated ranking, greedy selection can reinforce historical bias. Constraints involving fairness, privacy, diversity, or long-term impact may not form a matroid and may require multi-objective optimization or constrained approximation.

Contemporary research extends greedy ideas to submodular maximization, online algorithms, streaming, distributed optimization, and adaptive selection. For a monotone submodular function under a cardinality constraint, the classical greedy algorithm achieves a (1 − 1/e) approximation under standard assumptions. Here, diminishing returns replace exact exchangeability; the result is an approximation guarantee rather than exact optimality.

In large-scale AI systems, greedy selection is often combined with lazy evaluation, stochastic estimates, parallel processing, and learned scoring functions. A learned score can improve empirical performance, but it does not automatically preserve a theoretical guarantee. The objective, constraints, data distribution, and evaluation protocol must all be specified.

Chapter Summary

Greedy algorithms make irreversible local choices and are effective when the problem has a safe-choice structure. Correctness commonly depends on the greedy-choice property and optimal substructure. Exchange arguments transform an optimal solution into one containing the greedy choice, while cut properties justify minimum-spanning-tree algorithms. Activity selection, fractional knapsack, Huffman coding, Kruskal’s algorithm, and Prim’s algorithm illustrate exact greedy success.

Matroids formalize the independence and exchange structure behind weighted greedy optimization. Graphic and partition matroids provide important examples. In contrast, 0/1 knapsack, arbitrary coin change, and general set cover show that local quality alone is not enough. When exact greedy optimality fails, approximation guarantees, dynamic programming, search, or mathematical programming may be appropriate. In AI and ML, greedy feature selection can be practical but must be evaluated for interactions, leakage, stability, fairness, and generalization.

Key Terms

Greedy algorithm: An algorithm that repeatedly makes an irrevocable locally preferred choice.

Feasible solution: A solution satisfying all problem constraints.

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

Optimal substructure: The property that optimal residual solutions occur within optimal complete solutions.

Exchange argument: A proof that replaces part of an optimum with a greedy choice without worsening quality.

Activity selection: Selecting the maximum number of pairwise compatible intervals.

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

Value density: Value per unit weight, ρᵢ = vᵢ ÷ wᵢ.

Minimum spanning tree: A minimum-weight tree connecting all vertices of a connected weighted graph.

Cut: A partition of graph vertices into two nonempty parts.

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

Kruskal’s algorithm: An edge-ordered MST algorithm that rejects cycle-forming edges.

Prim’s algorithm: An MST algorithm that expands one connected tree using a light boundary edge.

Prefix-free code: A code in which no codeword prefixes another.

Matroid: A finite independence system satisfying nonemptiness, heredity, and exchange.

Basis: A maximal independent set in a matroid.

Graphic matroid: The matroid whose independent sets are forests of a graph.

Approximation guarantee: A proven bound relating an algorithm’s result to the optimum.

Submodularity: A diminishing-returns property used in approximation algorithms.

Review Questions

Short Answer Questions

1. What distinguishes feasibility from optimality in a greedy algorithm?
2. State the greedy-choice property.
3. Why does earliest finish time solve activity selection?
4. What is the cut property for minimum spanning trees?
5. List the three matroid axioms.

Long Answer Questions

1. Give a complete exchange-argument proof for the activity-selection algorithm.
2. Explain Kruskal’s algorithm, including its data structure and complexity.
3. Prove why density ordering solves fractional but not generally 0/1 knapsack.
4. Explain Huffman coding and its greedy optimality argument.
5. Compare matroid greedy optimization with greedy set cover.

Analytical / Application Questions

1. Construct a coin system and target for which greedy change-making is suboptimal, and prove the claim.
2. Given a weighted graph, determine an MST using both Kruskal’s and Prim’s algorithms and compare their intermediate choices.
3. Design a greedy feature-selection experiment that controls validation leakage, evaluates stability, and tests whether the resulting model is fair across relevant groups.

Multiple Choice Questions with Answers

Question 1

Which property is directly used in an exchange argument?

A. A greedy choice can be included in some optimal solution without worsening it.

B. Every feasible solution has the same objective value.

C. All edge weights must be distinct.

D. The search space must be continuous.

Correct Answer: A. A greedy choice can be included in some optimal solution without worsening it.

Question 2

What is the correct greedy rule for activity selection?

A. Choose the longest activity first.

B. Choose the activity with the earliest finish time.

C. Choose the activity with the latest start time only.

D. Choose the activity with the greatest duration.

Correct Answer: B. Choose the activity with the earliest finish time.

Question 3

For fractional knapsack, items are ordered by which quantity?

A. Weight minus value

B. Total weight

C. Value divided by weight

D. Value plus weight

Correct Answer: C. Value divided by weight

Question 4

What does Kruskal’s algorithm reject?

A. Every edge with positive weight

B. Edges that would create a cycle

C. The lightest edge in the graph

D. Edges incident to the starting vertex

Correct Answer: B. Edges that would create a cycle

Question 5

A light edge crossing a cut is called safe because it can be included in:

A. Some minimum spanning tree

B. No spanning tree

C. Only a directed cycle

D. Every shortest path

Correct Answer: A. Some minimum spanning tree

Question 6

Which structure supports efficient cycle checks in Kruskal’s algorithm?

A. Stack

B. Queue

C. Disjoint-set union

D. Binary search tree of vertices only

Correct Answer: C. Disjoint-set union

Question 7

Which condition is NOT one of the matroid axioms stated in the chapter?

A. Nonemptiness

B. Hereditary property

C. Exchange property

D. All elements must have equal weight

Correct Answer: D. All elements must have equal weight

Question 8

For coin denominations 1, 3, and 4 with target 6, what does greedy choose?

A. Two coins: 3 and 3

B. Three coins: 4, 1, and 1

C. Six coins of value 1

D. One coin of value 6

Correct Answer: B. Three coins: 4, 1, and 1

Question 9

Why can greedy feature selection fail to find the best feature subset?

A. Features can have interaction effects.

B. Features cannot be evaluated numerically.

C. Validation is never needed.

D. Greedy algorithms always select every feature.

Correct Answer: A. Features can have interaction effects.

Question 10

The classical greedy guarantee for monotone submodular maximization under a cardinality constraint is:

A. Exactly zero

B. 1 − 1/e approximation

C. Always twice the optimum

D. No possible bound under the stated assumptions

Correct Answer: B. 1 − 1/e approximation