Chapter 4: Greedy Algorithms

Greedy algorithms build up solutions in small steps, “taking as much as they can” to reduce the size of the problem at hand. It may be easy to come up with greedy solutions for any kind of problem, but greedy solutions are not always optimal. In this chapter we will learn how to choose rules that make greedy solutions work and prove that they are optimal.

This section introduces a concrete example of greedy algorithms: interval scheduling. This basic problem was mentioned in Chapter 1 (as one of the “five representative problems”). We learn how to prove that a greedy algorithm produces an optimal solution to some problem. This can be done by considering some unknown optimal solution O, and showing that the greedy algorithm produces a solution identical to that one, or one that is just as good. For example, in the interval scheduling problem, we can show that the optimal greedy algorithm (the one that recursively selects the interval that ends first and deletes all intervals that are incompatible with that one) “stays ahead” of all other solutions.

Problems “like” this one could be very difficult. For instance, new requests could be made “in real time” and the algorithm would have to deal with that. Alternatively, there could be multiple resources that we could allocate time to. The point of this section was to show a basic example of the greedy algorithm at work, as well as give the reader a taste of what's to come.

Now we consider a different (cooler) interval scheduling problem. This time, for each of n requests to use a resource, the request only tells us about the time it will take to complete its work and the deadline for that job. The goal of our solution is to produce a schedule of jobs that has the minimum possible “maximum lateness” - this means that for each job, we calculate its individual lateness, and the maximum of those is the maximum lateness for the whole solution.

It turns out that a greedy algorithm provides the optimal solution to this problem. The Earliest Deadline First rule is the basis for this greedy algorithm. This algorithm is optimal because…

• (4.7) There is an optimal solution with no idle time.
• (4.8) All schedules with no inversions and no idle time have the same maximum lateness.
• (4.9) There is an optimal schedule that has no inversions and no idle time.
• (4.10) The schedule produced by the greedy algorithm has optimal maximum lateness.

Note: these proofs are (seem?) conceptually obvious but take many pages of ink.

This section refers to situations in which only a small amount of information can be accessed quickly and a large amount of information requires significantly more time to access. In computer memory, information in the cache is the fastest to access. “Memory hierarchy.” We need to know what information should be put in the cache, and which should be left out or evicted. Whenever an item needs to be accessed from “main memory” it must be brought into the cache. If the cache is full when this happens, then some information from the cache needs to be evicted. This is called a cache miss - something that we try to avoid.

The Farthest-in-Future Algorithm says that whenever a new piece of information needs to be brought into the cache, the item that is needed farthest into the future should be evicted. This algorithm is optimal in that the schedule of evictions it produces “incurs the minimum possible number of [cache] misses.” As with the interval scheduling problem (4.1), this algorithm assumes knowledge of future memory requests. In the case of unknown future requests, the LRU (Least-Recently-Used) Principle has proven effective: if a piece of information in cache has been used recently, then it is likely that it will be accessed again soon; if a piece of information has not been used recently, then it is safe to assume that it has a lesser chance of being used in the near future.

Naturally we want to find the shortest path between two nodes (s,t) in a network.* Dijkstra's Algorithm does this in the following way. First, it initializes the distance to s to be 0 and that to every other node to be “infinity.” S is the set of nodes whose distances from s is assuredly minimal. This is also called the blob. Certainly s is in the blob since its distance from s is 0. This could be false if there were negative-length edges, and while there are shortest-path algorithms for those cases, we will assume that every edge length is positive. Dijkstra's Algorithm grows the blob by following its nodes' outgoing edges to nodes outside the blob and modifying those nodes' distance variables. At any time during the running of the algorithm, the blob will by definition contain nodes u for which d(u) is minimal. Since when the algorithm completes, the blob contains every node in s's connected component, it follows that the d(u)s for every node in that graph is shortest.

The nodes in S are maintained in a priority queue. The value of each node is the distance to that node from s. Initially, d(u) = infinity for each u, and d(s) = 0.

Dijkstra's Algorithm is O(mlogn). m comes from iterating through each edge once. The log(n) comes from the heap operations used to maintain the priority queue.

*This section refers to directed graphs but the solution will also work for undirected graphs.

Situation: There are n locations. Every edge has a cost. We want the subset of edges that connects all locations and costs as little as possible.

(4.16) Let T be a minimum cost solution to the network design problem. Then (V, T) is a tree. Algorithms to find the minimum spanning tree for a graph:

• Kruskal's Algorithm:
• Prim's Algorithm: O(m+n)
• Reverse-Delete Algorithm:

“When Is It Safe to Include an Edge in the Minimum Spanning Tree?”

CUT PROPERTY

(4.17) Assume that all edge costs are distinct. Let S be any subset of nodes that is neither empty nor equal to all of V, and let edge e = (v,w) be the minimum-cost edge with one end in S and the other in V - S. Then every minimum spanning tree contains the edge e.

Algorithms that apply this property: Kruskal, Prim

“When Can We Guarantee an Edge Is Not in the Minimum Spanning Tree?”

CYCLE PROPERTY

(4.20) Assume that all edge costs are distinct. Let C be any cycle in G, and let edge e = (v,w) be the most expensive edge belonging to C. Then e does not belong to any minimum spanning tree of G.

Algorithms that apply this property: Reverse-Delete

Under construction…