Greedy method and exchange argument

Why it exists

Many optimisation problems ask for the best selection out of an astronomical number of possibilities. A greedy algorithm avoids the search: at each step it takes the choice that looks best right now and never reconsiders. Greedy algorithms are usually the simplest and fastest (often $O(n \log n)$, dominated by a sort), but they are correct only for problems with the right structure, and the main skill tested in exams is telling whether greedy works and why. This page gives the criteria and the proof method; the next pages apply them to scheduling, knapsack and coding, and later pages to spanning trees and shortest paths.

Prerequisites

You need to be able to count the running time of a loop with a sort (analysing loops).

Precise definitions

Greedy algorithm. It builds a solution step by step. At each step it picks, among the options currently allowed, the one that is best by a fixed local rule (largest, earliest, cheapest, ...), commits to it, and shrinks the problem.

Greedy-choice property. There is an optimal solution that contains the greedy choice. (So committing to it loses nothing.)

Optimal substructure. After the greedy choice is made, what remains is a smaller problem of the same kind, and an optimal solution of the whole contains an optimal solution of the smaller problem.

A greedy algorithm is correct when both properties hold. Dynamic programming also needs optimal substructure but not the greedy-choice property: it tries all choices (dynamic programming).

Exchange argument (the standard proof). Take any optimal solution $O$. Show that $O$ can be changed, one step at a time, into the greedy solution $G$ without getting worse: swap a part of $O$ for the greedy choice and show the value does not decrease. Since each swap keeps optimality, $G$ is optimal.

Greedy stays ahead (the other method). Show by induction that after every step the greedy partial solution is at least as good as the partial solution of any other algorithm, by a measure that implies the final claim.

A counterexample is the only way to show that a greedy rule is wrong, and one suffices.

How it works

A first proof: shortest processing time first

$n$ jobs with processing times $p_1, \ldots, p_n$ are done one after another on one machine. Job $i$ finishes at its completion time $C_i$ (the sum of the processing times up to and including it). Goal: minimise the total (equivalently the average) completion time. Rule: shortest job first.

Exchange argument. Take any order and look at two adjacent jobs $i$ then $j$ with $p_i > p_j$ (a longer job before a shorter one), starting at time $t$. Their completion times are $t + p_i$ and $t + p_i + p_j$, with sum $2t + 2p_i + p_j$. After swapping them they are $t + p_j$ and $t + p_j + p_i$, with sum $2t + 2p_j + p_i$. The difference is $p_i - p_j > 0$: the swap makes the total smaller, and no other job is affected (the pair finishes at the same time $t + p_i + p_j$ in both orders). So any order that has a longer job directly before a shorter one can be improved; the only order with no such pair is the sorted one, which is therefore optimal. (An independent check tried every order of hundreds of random job sets: the sorted order always gave the minimum.)

The algorithm is a sort: $\Theta(n \log n)$. Another rule with the same style of proof: to minimise the maximum lateness (completion time minus deadline), do the jobs in order of earliest deadline first.

When greedy fails: making change

Pay an amount with as few coins as possible. Greedy rule: take the largest coin that fits, repeat. The program compares greedy with the exact optimum (computed by dynamic programming) for three coin systems.

#include <stdio.h>
 
/* coins[] is in decreasing order; the greedy method takes as many of the largest coin as possible, then the next, ... */
static int greedy(const int coins[], int k, int amount) {
    int count = 0;
    for (int i = 0; i < k; i++) {
        count += amount / coins[i];
        amount %= coins[i];
    }
    return count;
}
 
/* the fewest coins, by dynamic programming over all amounts up to the given one */
static int optimal(const int coins[], int k, int amount) {
    int best[256];
    best[0] = 0;
    for (int a = 1; a <= amount; a++) {
        best[a] = 1 << 20;
        for (int i = 0; i < k; i++)
            if (coins[i] <= a && best[a - coins[i]] + 1 < best[a]) best[a] = best[a - coins[i]] + 1;
    }
    return best[amount];
}
 
int main(void) {
    int a[4] = {25, 10, 5, 1}, b[3] = {4, 3, 1}, c[3] = {10, 6, 1};
    int amounts_a[4] = {30, 41, 63, 99}, amounts_b[5] = {5, 6, 7, 8, 9}, amounts_c[2] = {12, 30};
    for (int t = 0; t < 4; t++) printf("A %2d greedy %d optimal %d\n", amounts_a[t], greedy(a, 4, amounts_a[t]), optimal(a, 4, amounts_a[t]));
    for (int t = 0; t < 5; t++) printf("B %2d greedy %d optimal %d\n", amounts_b[t], greedy(b, 3, amounts_b[t]), optimal(b, 3, amounts_b[t]));
    for (int t = 0; t < 2; t++) printf("C %2d greedy %d optimal %d\n", amounts_c[t], greedy(c, 3, amounts_c[t]), optimal(c, 3, amounts_c[t]));
    int bad_a = 0, bad_b = 0, bad_c = 0;
    for (int x = 1; x <= 200; x++) {
        if (greedy(a, 4, x) != optimal(a, 4, x)) bad_a++;
        if (greedy(b, 3, x) != optimal(b, 3, x)) bad_b++;
        if (greedy(c, 3, x) != optimal(c, 3, x)) bad_c++;
    }
    printf("amounts 1 to 200 where greedy is not optimal: A %d, B %d, C %d\n", bad_a, bad_b, bad_c);
    return 0;
}

A 30 greedy 2 optimal 2
A 41 greedy 4 optimal 4
A 63 greedy 6 optimal 6
A 99 greedy 9 optimal 9
B  5 greedy 2 optimal 2
B  6 greedy 3 optimal 2
B  7 greedy 2 optimal 2
B  8 greedy 2 optimal 2
B  9 greedy 3 optimal 3
C 12 greedy 3 optimal 2
C 30 greedy 3 optimal 3
amounts 1 to 200 where greedy is not optimal: A 0, B 49, C 114

• System A, $\{1, 5, 10, 25\}$: greedy is optimal for every amount (none of $1 \ldots 200$ fails; it was also checked up to $1000$). Systems like this one are called canonical. The coins $\{1, 3, 9, 27\}$, powers of one base, are also canonical.
• System B, $\{1, 3, 4\}$: for the amount $6$ greedy takes $4 + 1 + 1$, three coins, but $3 + 3$ is two. The first failures are $6, 10, 14, \ldots$. The greedy choice "take the $4$" is not part of any optimal solution of $6$: the greedy-choice property fails.
• System C, $\{1, 6, 10\}$: for $12$, greedy takes $10 + 1 + 1$ but $6 + 6$ is better.

So the same rule is correct for one set of inputs and wrong for another. A proof (or a known theorem) is needed each time; a few examples that work prove nothing.

Where greedy works in the syllabus

Where greedy fails (and dynamic programming or search is needed): 0/1 knapsack, shortest paths with negative edges, general coin systems, travelling salesman.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The method is applied in activity selection and fractional knapsack, Huffman coding, spanning trees and Dijkstra's algorithm. When greedy fails the usual tool is dynamic programming. Sorting costs come from the sorting pages and loop counting from analysing loops.

PYQs

Consider the following table:

Algorithms
Design
Paradigms
P
Kruskal
i
Divide and
Conquer
Q
Quicksort
ii
Greedy
R
Floyd-
Warshall
iii Dynamic
Programming

Given below are some algorithms, and some
algorithm design paradigms.
List - I
P. Dijkstra's Shortest Path
Q. Floyd-Warshall algorithm to compute all
pairs shortest path
R. Binary search on a sorted array
S. Backtracking search on a graph
List – II
i. Divide and Conquer
ii. Dynamic Programming
iii. Greedy design
iv. Depth-first search
v. Breadth-first search
Match the above algorithms on the left to the
corresponding design paradigm they follow.

Match the following:

(P) Prim's algorithm for
minimum spanning tree
(i) Backtracking
(Q) Floyd-Warshall
algorithm for all pairs
shortest paths
(ii) Greedy
method
(R) Mergesort
(iii) Dynamic
programming
(S) Hamiltonian circuit
(iv) Divide and
conquer

Self-check

Revision card

References