9. Greedy Approximation Algorithms and Layering

In CSCI 3110, you should have received a first introduction to greedy algorithms. The main characteristic of a greedy algorithm is that it makes "local" choices: It constructs a solution one choice at a time, and it makes each choice based on what seems best at the moment, without consideration for how this choice affects future choices. For example, Kruskal's algorithm builds a minimum spanning tree by repeatedly picking the cheapest edge that can still be added to the current partial spanning tree without creating a cycle. We were able to prove that once we obtain a tree, the result must be a minimum spanning tree.

The problems discussed in CSCI 3110 had the remarkable property that it was possible to arrive at a globally optimal solution by making such local choices. For many problems, this is not the case: We may be able to obtain a good solution by making local choices, but the solution may not be optimal. Sometimes, making greedy choices may lead to arbitrarily bad solutions. For other problems, greedy choices may be the basis for very good heuristics in practice. While heuristics may work very well in practice, they have the disadvantage that they usually do not provide any provable guarantees on how much worse the computed solution is than an optimal solution. In this chapter, we consider a number of problems for which we can prove that a greedy algorithm computes a \(c\)-approximation of an optimal solution, for some small factor \(c\).

• As a warm-up exercise, we start with the bin packing problem in Section 9.1. We prove that a very simple greedy algorithm produces a \(2\)-approximation of an optimal solution.

• The set cover problem is a generalization of the vertex cover problem, which I introduced in Chapter 8. We discuss two algorithms for the set cover problem. A fairly natural greedy algorithm computes an \(O(\lg n)\)-approximation of an optimal set cover. We discuss this algorithm in Section 9.2. A second algorithm, discussed in Section 9.3, computes an \(f\)-approximation, where \(f\) is the maximum number of sets in the input that any element occurs in. This algorithm is based on an interesting technique, called layering. The main idea of layering is to slice (layer) the input into subproblems such that a good approximation of an optimal solution can be obtained easily on each layer. By combining the solutions on the different layers, we then obtain a good approximation for the entire input. It turns out that every approximation algorithm for the set cover problem achieves one of these two approximation ratios: \(f\) or \(O(\lg n)\).

• We conclude the chapter by discussing, in Section 9.4, the feedback vertex set problem, which is a second problem for which layering produces a good approximate solution.