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.

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. Remember the cut property and the cycle property. Here are descriptions of the three greedy algorithms.

• Kruskal: cut property;
• Prim: O(mlogn); cut property;
• Reverse-Delete: cycle property;

The title says it all. We want to know the connected components of a graph, but we don't want to recompute them every time that an edge is added to the graph. A solution to this problem is the the Union-Find structure. It supports three operations:

1. MakeUnionFind(S): returns a Union-Find data structure on the set S, where every element begins in its own component; O(n).
2. Find(u): returns the name of the component that u belongs to; O(log n).
3. Union(A,B): merges two components (A,B) into one component; O(log n).

Efficiency (4.25): Kruskal's Algorithm can be implemented on a graph with n nodes and m edges to run in O(m logn) time.

Situation: Given a collection of objects, we want k clusters (but not any clustering, we want the “clustering of maximum spacing”). Brute force approach to finding the best clustering is terribly inefficient, since there are “exponentially many different k-clusterings of a set U.” The answer is related to minimum spacing trees.

A variation of Kruskal's Algorithm solves it (4.26) The components C1, C2, …, Ck formed by deleting the k - 1 most expensive edges of the minimum spanning tree T constitute a k-clustering of maximum spacing.

Huge research area. Think languages. If there are n letters in a language, it's possible to encode the letters in log(n) bits. But we know that letters come up with different frequencies. Suppose we are given the individual frequencies of each letter; is it possible to encode the more frequent letters with fewer bits so as to reduce the average bits per letter (ABL)?

Yeah, Huffman coding is one way.

Under construction…