Greedy Algorithms

Introduction

Greedy algorithms build up a solution piece-by-piece, taking locally optimal choices at each step (without reconsidering past choices). For certain problems, locally optimal choices result in a globally optimal solution; in others, they produce a near-optimal one (see approximation algorithms). In this section, we explore greedy algorithms that produce an optimal solution, as well as two styles of correctness proofs for greedy algorithms: an exchange argument or a greedy stays ahead argument.

Proof Strategies

Greedy Stays Ahead

A greedy stays ahead argument shows that your greedy solution maintains some property that is "more extreme" than any other optimal solution at every step, and that this implies optimality. The general structure is:

1. Find a property of your greedy solution that is "more extreme" (e.g., smaller or larger) than any other solution after each step (this usually relates to your greedy criterion).
2. Make sure that extremity of this characteristic implies optimality.
3. Prove via induction that the greedy solution actually maintains this property at every step.
4. Conclude that your solution is as good as optimal.

note

It is very important that you explain why your property implies optimality! A common mistake is to identify a property that greedy maintains without connecting it to the size or quality of the final solution. The property alone means nothing; you need to argue that if greedy stays ahead in this metric, it must produce a solution at least as good as any optimal solution.

Exchange Argument

Suppose that our greedy algorithm produces a solution $A$. Our goal with using an exchange argument is to prove that anything in an optimal solution $O$ can be swapped with anything in our solution $A$ without losing optimality.

1. Assume that your greedy solution and the optimal solution you choose differ in some way. (If this is not the case, then $A = O$ and we are done!).
2. Show that it is possible to make progress, that is “exchange” elements in $O$ to make it more similar to your solution $A$ while preserving the optimality of $O$.
3. Show that this exchange progress terminates, and when it does $A = O$ where $O$ is optimal. Then, $A$ is at least as good as $O$, so $A$ is optimal.

note

Make sure you exchange elements from $O$, not $A$! If you exchange elements from $A$, then you change the solution that you trying to prove is optimal!

Sample Problem: Interval Scheduling

Suppose we have a machine $M$ that can process at most $1$ job at a time. We have $n$ job requests, each with a start time $s_i$ and end time $f_i$ for $1 \le i \le n$ with $s_i < f_i$. Our objective is to schedule the maximum number of non-conflicting jobs. Formally, we want to maximize the size of the set of non-conflicting jobs $S \subseteq [n]$ that we want to schedule on $M$. We say two jobs $i$ and $j$ are non-conflicting if:

• job $i$ happens before job $j$: $s_i \le f_i \le s_j \le f_j$
• job $j$ happens before job $i$: $s_j \le f_j \le s_i \le f_i$

Give an efficient algorithm that solves this problem.

Solution

To solve this problem, we want to pick the jobs with the earliest remaining finish times. This way, we leave the most remaining time for future jobs, maximizing our future options.

R = set of all jobs, A = []
while R is not empty:
    pick job i in R with the earliest remaining finish time and add it to A
    remove all jobs in R that conflict with i
output A

Before we prove this solution, it is a good exercise is to try and disprove bad greedy strategies. Can you find a counterexample for the following greedy approaches? For each approach, you can assume that after a job is selected, you remove all jobs that conflict with it.

• Select the remaining job with the earliest start time.

Solution

Suppose we had 3 jobs.

• Job 1: $s_1 = 1$, $f_1 = 10$
• Job 2: $s_2 = 2$, $f_2 = 3$
• Job 3: $s_3 = 4$, $f_3 = 5$

With our earliest start time strategy, we take job 1, which conflicts with both other remaining jobs. The optimal solution involves taking jobs 2 and 3 (which don't overlap). Therefore, this straetgy is not optimal.

• Select the remaining job with the shortest interval (the one that minimizes $f_i - s_i$).

Solution

Consider the following set of 3 jobs.

• Job 1: $s_1 = 1$, $f_1 = 5$
• Job 2: $s_2 = 4$, $f_2 = 7$
• Job 3: $s_3 = 6$, $f_3 = 10$

Taking the shortest job (2) locks us out of taking either job 1 or job 3. However, since job 1 and 3 don't overlap, taking both of them would be the optimal solution. Thus, selecting the remaininng job with the shortest interval is not the optimal solution.

• Select the remaining job with the latest finish time.

Solution

Consider the following 3 jobs.

• Job 1: $s_1 = 1$, $f_1 = 5$
• Job 2: $s_2 = 6$, $f_2 = 7$
• Job 3: $s_3 = 1$, $f_3 = 11$

With our greedy strategy, we would schedule job 3, and this would be the only job we would do. However, the optimal solution is to do jobs 1 and 2 (so this proposed greedy strategy is not optimal).

We can prove that our strategy of picking the earliest remaining finish time is optimal strategy. We show this using both greedy-stays-ahead and exchange argument proofs. For a problem set or exam, you'll only need to select one proof style, so be sure to pick the proof style that is the most straightforward!

Proof: Greedy Stays Ahead

Proof coming soon!

Proof: Exchange Argument

Proof coming soon!

Runtime Analysis

We can make our algorithm run in $O(n \log n)$ time. We first sort the $n$ jobs in order of finishing time in $O(n \log n)$ time. We select jobs by processing the intervals in this sorted order, maintaining the finish time of the most recently selected job; for each job, we check whether its start time is at least this finish time, which takes $O(1)$ time per job, giving $O(n)$ total. The overall runtime is dominated by the sort, so the algorithm runs in $O(n \log n)$ time.

Minimum Spanning Tree

Suppose we have an connected, undirected graph $G = (V, E)$, where edge $e \in E$ has some positive edge weight $c_e$. We want to find the a subset of the edges $T \subseteq E$ such that the graph $(V, T)$ is still connected and the sum of edge costs $\sum_{e \in T} c_e$ is minimized. We call $T$ the minimum spanning tree of our graph $G$.

For example, suppose we have a graph:

Can you identify the minimum spanning tree?

Solution

One spanning tree is $\{AB, BC, BD\}$, which connects all four vertices with total cost $1 + 2 + 4 = 7$. Another spanning tree is $\{AC, BC, CD\}$, which also connects all four vertices, but has total cost $3 + 2 + 5 = 10$.

The minimum spanning tree is

$$T = \{AB, BC, BD\}$$

with total cost $7$. We do not include $AC$, because $A$ and $C$ are already connected through $ABC$ at lower cost, and we do not include $CD$, because $D$ is already connected through $BD$ at lower cost.

We prove that a minimum spanning tree $T$ has no cycles.

Proof

Suppose for contradiction's sake that our minimum spanning tree $T$ has a cycle. Deleting any edge $e$ from the cycle will make the MST cheaper (since all weights are positive). Furthermore, the graph remains connected after deleting an edge (the two endpoints of $e$ are still connected by the rest of the cycle). This contradicts the minimality of our claimed MST because we have a spanning tree with a lower cost; therefore, a MST cannot contain a cycle.

In the following section, we study Kruskal's and Prim's algorithm to find a graph's minimum spanning tree (MST).

Kruskal's Algorithm

Kruskal's algorithm builds our spanning tree by greedily selecting the lowest cost edge that does not form a cycle. Suppose that our graph $G = (V, E)$ has $n$ vertices and $m$ edges.

sort all edges based on weight
S = {}, T = {}
while S != V:
    consider edge e = (u, v) with lowest edge weight
    if adding e to T does not create a cycle:
        add u, v to S
        add edge e to T
output T

To implement this into code, we can use a union find data structure; we can easily see if adding an edge will form a cycle by checking if its two endpoints belong to the same connected component. This lets us to process each edge in near $O(1)$ time. However, our main bottleneck of our algorithm is the $O(m \log m)$ time to sort all edges. Since $m \le n^2$, then this turns into $O(m \log n)$ overall time complexity.

Prim's Algorithm

Another strategy for building a MST is to grow it from a root node. Known as Prim's algorithm, we grow the tree outward, greedily selecting the node that can be attached using the least cost edge. Calling our root or starting node $s$, here is the pseudocode for Prim's algorithm:

S = {s}, T = {}
while S != V:
    find v not in S such that edge e = (u, v) has minimum weight 
        among all edges with one endpoint in S and other in S \ V
    add v to S
    add e to T
output T

We can implement Prim's algorithm using a min priority queue. We can extract each vertex exactly once from the priority queue, for a time complexity of $O(n \log n)$. Additionally, after selecting a node, we need to update the edge costs of all its neighbors (in case there is now a cheaper path to an undiscovered node). We observe that the total number of checks done is bounded by $\sum_{u \in V} \deg(u) = 2m$. So, the total number of potential updates is $O(m)$, each costing $O(\log n)$, giving $O(m \log n)$ time complexity for the update step. Since $n \le m$, the overall time complexity is $O(m \log n)$.

Visualization Demo

Minimum Spanning Tree

Start at A

The tree contains A. Prim looks only at edges crossing from the tree to the outside.

Step 1 / 6

Grow one tree by repeatedly choosing the cheapest crossing edge.

Chosen edges0

Total weight0

A-B4

A-C3

B-C1

B-D2

C-D3

C-E5

D-E1

D-F6

E-F2

accepted current candidate

Cut Property

When building a MST, we'd like a way to confirm that a particular edge must belong to it (ideally without examining every spanning tree!). This is where the cut property comes in.

Definition: Cut

A cut of a graph $G = (V, E)$ is a partition of the vertex set into two nonempty, disjoint sets $S$ and $V \setminus S$. An edge $e = (u, v)$ crosses the cut if one endpoint lies in $S$ and the other lies in $V \setminus S$.

Cut Property. Let $(S, V \setminus S)$ be any cut of a connected, weighted graph $G$. If $e$ is an edge of minimum weight among all edges crossing the cut, then there exists a minimum spanning tree of $G$ that contains $e$. If all edge weights are distinct, this strengthens to: every MST contains $e$.

Proof: Let $T$ be any MST $G$, and suppose $T$ does not contain $e = (u, v)$.

1. Since $T$ is a spanning tree, there is a unique path $P$ in $T$ from $u$ to $v$.
2. Because $u$ and $v$ lie on opposite sides of the cut, $P$ must cross the cut at least once. Let $e'$ be an edge of $P$ that crosses the cut.
3. By assumption, $c_e \le c_{e'}$, since $e$ is a minimum-weight crossing edge.
4. Form $T' = T - e' + e$. Removing $e'$ from $T$ splits it into two components; adding $e$ reconnects them (since $e$ also crosses the cut), so $T'$ is again a spanning tree.
5. Let $w(T)$ be the total edge weight of spanning tree $T$. We have that $w(T') = w(T) - c_{e'} + c_e \le w(T)$

Since $T$ was minimum, $w(T') \ge w(T)$ as well, so $w(T') = w(T)$, meaning $T'$ is also an MST, and it contains $e$.

To prove the stengthening of our claim, now assume that all edge weights are distinct. Suppose for contradiction's sake that some MST $T$ does not contain $e$. Consider a similar argument with the path $P$, crossing edge $e' \ne e$, and the inequality $c_{e} \le c_{e'}$ (since $e$ is the minimum cost edge crossing that cut). Since weights are distinct and $e \ne e'$, the previous inequality is strict:

$$\begin{align*} c_{e} < c_{e'} \end{align*}$$

Consider the exchange of $e'$ for $e$ to produce new tree $T'$.

$$w(T') = w(T) - c_{e'} + c_{e} < w(T)$$

so $T'$ is a spanning tree with less total edge weight than $T$, contradicting the minimality of $T$. Hence, every MST must contain $e$.

Proof of Prim's Algorithm

Now we prove the correctness of Prim's algorithm using an exchange argument. Let $A = \{e_1, e_2, \dots, e_{n - 1}\}$ be the edges selected by Prim's algorithm, in the order they were added, and let $S_k$ denote the set of vertices spanned by $\{e_1, \dots, e_k\}$ (so $S_0 = \{s\}$). Let $O$ be any MST. If $A = O$, we are done. Otherwise, consider the case $A \ne O$.

Since $A \ne O$, there is some smallest index $k$ such that $e_k \notin O$ (so $e_1, \dots, e_{k-1} \in O$, but $e_k \notin O$). Write $e_k = (u, v)$ with $u \in S_{k-1}$ and $v \notin S_{k-1}$; by definition of Prim's algorithm, $e_k$ is a minimum-weight edge crossing the cut $(S_{k-1}, V \setminus S_{k-1})$.

Since $O$ is a spanning tree, there is a unique path $P$ from $u$ to $v$ in $O$. Since $u \in S_{k-1}$ and $v \notin S_{k-1}$, $P$ must cross the cut $(S_{k-1}, V\setminus S_{k-1})$ at some edge $e'$. Because $e_k$ is a minimum-weight edge crossing this cut, we have $c_{e_k} \le c_{e'}$.

Note also that $e' \ne e_i$ for any $i < k$: each $e_i$ (for $i < k$) has both endpoints in $S_{k-1}$, so it cannot cross the cut, while $e'$ does.

Now form $T' = O - e' + e_k$. Since $e'$ lies on the path between $u$ and $v$ in $O$, removing it separates $u$ from $v$; adding $e_k = (u,v)$ back reconnects them, so $T'$ is again a spanning tree. Its weight is

$$w(T') = w(O) - c_{e'} + c_{e_k} \le w(O).$$

Since $O$ is optimal, $w(T') \ge w(O)$ as well, so $w(T') = w(O)$, meaning $T'$ is also an MST. Moreover, since $e' \ne e_1, \dots, e_{k-1}$, none of these edges were removed, so $T'$ contains $e_1, \dots, e_{k-1}, e_k$: one more edge of $A$ than $O$ did.

We can repeat this process: at each step, we exchange one edge of our current optimal tree for the next edge of $A$ it disagrees on, strictly increasing the number of edges shared with $A$ while preserving optimality. Since there are only $n-1$ edges total, this process terminates after at most $n-1$ exchanges, at which point our tree equals $A$ exactly. Since every tree produced along the way is an MST, $A$ is an MST.

Practice

Problem 1. Suppose we have a undirected graph $G = (V, E)$ with edge weights $c_e > 0$ for each edge $e \in E$, and a minimum spanning tree $T$ in this graph. Suppose we squared the cost of each edge $e \in E$, i.e. let $c'_e = c_e^2$. Is $T$ still a MST with these new edge weights? If yes, provide a brief explanation; if no, provide a counterexample.

Solution

True. Recall that the MST produced by Kruskal's algorithm depends only on the sorted order of the edge weights. Squaring the weights does not change their relative ordering (since all the weights are positive).

Problem 2. [Task Scheduling] Suppose you have $n$ tasks to complete. Task $i$ takes $p_i > 0$ time to complete and has priority $q_i > 0$, representing how costly it is to wait and not do the task. If task $i$ is completed at time $T_i$, then the total cost is $\sum_{i = 1}^n q_i T_i$. Your goal is to decide what order to do the tasks in order to minimize this total.

Consider the following two greedy strategies:

• Most important task: do tasks in decreasing order of $q_i$.
• Best value-per-minute: do tasks in decreasing order of the ratio $q_i / p_i$.

Assume all task times, priority values, and ratios are distinct. For both strategies, prove that it gives the optimal schedule or provide a counterexample.

Solution

Most important task. This is not optimal. Consider a scenario with two tasks.

• Task 1: $p_1 = 100$, $q_1 = 2$
• Task 2: $p_2 = 1$, $q_2 = 1$

Using the greedy strategy, we first do task 1. This gives us a total cost of $100 \cdot 2 + 101 \cdot 1 = 301$. However, if we were to do task 2 first, we would end up with a lower cost of $1 \cdot 1 + 101 \cdot 2 = 203$. Thus, doing the most important tasks first is not an optimal strategy.

Best value-per-minute. This is optimal. We prove this via an exchange argument. Let the solution produced by our greedy algorithm be $A$, and the optimal ordering be $O$. If $A = O$, then we are done. Thus, we consider the case where $A \ne O$. If $A \ne O$, then the optimal ordering differs from the ordering specified by the greedy strategy. This means that there exists two tasks $i$ and $i + 1$ in our optimal ordering that do not respect the best value-per-minute ordering, i.e.

$$\begin{align*} \frac{q_i}{p_i} < \frac{q_{i+1}}{p_{i+1}} \end{align*}$$

Consider swapping the order in which the two tasks are completed. We observe that all the other finish times $T_j$ are the same (so the costs contributed by these other tasks stays the same). However, $F_i$ and $F_{i + 1}$ change.

• We complete task $i$ after task $i + 1$, so $F_{i}$ increases by $p_{i + 1}$. The overall cost contributed by task $i$ increases by $q_i \cdot p_{i + 1}$.
• We now complete task $i + 1$ first, so $F_{i + 1}$ decreases by $p_{i}$, reducing the cost by $q_{i + 1} \cdot p_{i}$.

Since we assumed $\frac{q_i}{p_i} < \frac{q_{i+1}}{p_{i+1}}$, we have $q_i \cdot p_{i + 1} < q_{i + 1} \cdot p_{i}$. Since the decrease is larger than the increase in total cost, swapping the order in which we complete task $i$ and $i + 1$ improves our total cost. This contradicts the assumption that we started with an optimal schedule. We can repeat this argument for any pair of tasks that doesn't use the best value-per-minute ordering. Therefore, the optimal ordering is by decreasing ratio $q_i / p_i$.

Problem 3. [Tunneling Dilemma] Caleb recently opened a new aquarium with a star attraction orca whale. The orca is showcased in any one of the aquarium's $n$ tanks. Lifting the orca out of the water by crane and transporting it from tank to tank is stressful and risky, so Caleb wants it to be able to swim between any two tanks instead.

For any pair of tanks $i \ne j$ with $1 \le i, j \le n$, Caleb can build a tunnel between them at construction cost $c_{ij} > 0$. The orca can swim through any tunnel he builds, in either direction, and may pass through intermediate tanks on the way. Caleb wants to choose a set of tunnels $F$ so that the orca can be moved from any tank to any other tank using only tunnels in $F$, minimizing the total construction cost $\sum_{\{i, j\} \in F} c_{ij}$.

Give a polynomial time algorithm that takes as input the costs $c_{ij}$ and outputs a minimum-cost set of tunnels meeting Caleb's requirement.

Hint

Can we represent the problem as a graph? Can we apply one of our MST algorithm to it?

Solution

Let $G$ be the complete graph on the $n$ tanks with edge weights $c_{ij}$. Run Kruskal's algorithm on $G$ and output the resulting tree $T$.

Correctness

Write $c(F) = \sum_{\{i,j\} \in F} c_{ij}$, and call $F$ feasible if the orca can reach any tank from any other using only tunnels in $F$. Since tunnels are bidirectional and the orca may pass through intermediate tanks, $F$ is feasible exactly when $(V, F)$ is connected.

Claim

Some optimal feasible set is a spanning tree of $G$.

Proof. Feasible sets exist since $G$ is complete, so let $F$ be optimal. It is connected. Suppose it contained a cycle $C$, and let $e = \{x, y\} \in C$. Then $(V, F - e)$ is still connected: any path using $e$ can be rerouted along the $x$-$y$ path $C - e$, giving a walk and hence a path. So $F - e$ is feasible with

$$c(F - e) = c(F) - c_e < c(F)$$

since $c_e > 0$, contradicting optimality. Thus $F$ is connected and acyclic, i.e. a spanning tree. $\blacksquare$

Every spanning tree is connected and hence feasible, so by the Claim the minimum over feasible sets equals the minimum over spanning trees. Kruskal is correct, so $T$ attains the latter, and $T$ is feasible. Hence $T$ is optimal.

Running time

$G$ has $m = \binom{n}{2} = O(n^2)$ edges, so Kruskal runs in $O(m \log m) = O(n^2 \log (n^2)) = O(n^2 \log n)$, which is polynomial.