Further Uses of Greedy and Local Search Algorithms
David P. Williamson, David B. Shmoys · Cambridge University Press eBooks · 2011
We have now concluded our initial introduction to the various techniques for designing approximation algorithms. In this second part of the book, we revisit each of these techniques and give additional applications of them. In some cases, these applications are recent or more advanced, but in others they are just a bit more technically involved, or are in some other way “nonintroductory.” Hence, this second part covers “further uses” of each technique, rather than “advanced uses” or “recent uses.” In this chapter, we look again at greedy and local search algorithms. We revisit the problem of minimizing the maximum degree of a spanning tree, and show that a variant of the local search algorithm described in Section 2.6 in which the local moves are carefully ordered results in a spanning tree whose maximum degree is within 1 of the optimum. When we revisit the technique of deterministic rounding in Chapter 11, we will show a similar result for a version of the problem in which there are costs on the edges. The bulk of this chapter is spent on greedy and local search algorithms for the uncapacitated facility location problem and the k -median problem. Simple local search algorithms for these problems have been known since the early 1960s. It is only relatively recently, however, that it has been shown that these algorithms produce provably near-optimal solutions. In Section 9.1, we show that a local search algorithm for the uncapacitated facility location problem gives a (3 + ε)-approximation algorithm for that problem.