Heuristic techniques for solving optimization problems in an approximate way have always been used throughout the history of computing and, in particular, since the early development of operations research. Nevertheless, no precise notion of approximation had been proposed until the late sixties and early seventies, when researchers introduced the notion of approximation with guaranteed performance ratio, n order to characterize those situations in which the approximate solution is provably close to an optimum one (e.g., within a factor bounded by a constant or by a slowly growing function of the input size).
Historically, the problems for which the first examples of this kind were proposed have been multiprocessor scheduling and bin packing problems, both related to computer resource management. Since then thousands of approximation algorithms, for all kinds of optimization problems, have been designed and published in the literature. However two aspects continued to remain unsolved until recently. First of all, while, in some cases, one was able to devise algorithms that could provide approximate solutions that were arbitrarily close to the optimum, in many cases the quality of the approximation was very poor (allowing, for example, a relative error of 50%) and it was not clear whether this was due to our lack in ability to design good approximation algorithms or to some intrinsic, structural properties of the problems. Second, some other problems were resisting to any type of attack and even very weak approximate solutions seemed to be impervious.
Recent results allow us to have now a more clear picture with respect to such aspects. On one side, in fact, extremely good approximation algorithms have been designed for some of the paradigmatic problems (such as the maximum satisfiability and maximum cut problems), good both with respect to the theoretical performance bounds and with respect to the practical applicability. At the same time a powerful (and surprising, we should say) technique, based on the notion of probabilistically checkable proofs, has been introduced for studying bounds in approximability of problems. By means of such techniques, it has been shown that some of the classical problems, such as the minimum graph coloring and the maximum clique problems, do not allow any approximation algorithm with guaranteed performance, while, for other problems, precise bounds to approximability have been found. In some cases, these bounds meet the degree of approximability that can actually be achieved and in such, unfortunately rare, cases (one of them is, indeed, the maximum satisfiability problem restricted to formulas with exactly three literals per clause), we may say that we possess the best possible approximation algorithm.
The content of the book is organized as follows. In the first chapter, after surveying classical topics concerning the complexity of decision problems, we introduce the basic notions of NP-hard optimization problems, and we give the motivation for studying approximation algorithms for such problems. The second chapter is devoted to basic techniques for the design of approximation algorithms and to the presentation of the first examples of such algorithms. In particular, algorithms based on general approaches such as the greedy approach, local search, and dynamic programming are considered, together with algorithms based on classical methods of discrete optimization, such as linear programming. The examples shown in this chapter testify that the quality of approximation that we may achieve in various cases may be quite different, ranging from constant to polynomial factors.
The third, fourth, and fifth chapters form the main part of the book in terms of positive results. In fact, they contain a large body of approximation algorithms and approximability results for several paradigmatic optimization problems. In Chap. 3, we concentrate on problems that belong to the so-called class APX, i.e., problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. After showing some examples of this kind of problems, we turn to the particular subclasses of APX consisting of problems for which any desired performance ratio can be obtained (i.e., the classes PTAS and FPTAS). In the same chapter, we give the first results that show that, unless P=NP, the approximability classes FPTAS, PTAS, and APX are strictly contained one into the other. Chapter 4 is devoted to problems that cannot be suitably classified in the above seen approximability classes. First, we consider problems that do not belong to APX and for which we can guarantee only a non-constant approximation ratio. Then, we consider problems that, while being outside of PTAS, indeed allow polynomial-time approximation schemes under a somewhat weaker notion of approximability, i.e., the asymptotic approximability. In Chap. 5, more advanced design techniques for approximation algorithms, based on linear and quadratic programming, are presented. Essentially, they are characterized by the use of randomization in rounding real solution to integer ones but, in all cases, we will see that the resulting algorithms can be transformed into deterministic ones without any loss in the approximation performance. Such techniques are, indeed, quite interesting from the application point of view, because their discovery led to very good approximation algorithms for some relevant optimization problems.
The sixth, seventh, and eighth chapters are devoted to the theoretical background and to the proof techniques that are needed to derive non-approximability results. First, in Chap. 6, after reviewing the formal basis of NP-completeness theory, the notion of probabilistically checkable proof is introduced and it is shown how, from the characterization of the class NP in terms of such proofs, a bound to the approximability of the maximum satisfiability problem and the non-approximability of the maximum clique problem can be derived. The almost complete proof of the above mentioned characterization (known as the PCP theorem) is given in Chap. 7. The result is quite involved and the proofs of some lemmas can be skipped in a first reading, but various ingredients of the main proof, such as the arithmetization of Boolean formulas, the linear function and the polynomial coding schemes, and the notion of transparent proof are important results per se and, in our opinion, deserve being known by any researcher working in this field. Finally, in Chap. 8, a systematic study of the approximability classes is performed. The chapter is based on the notion of approximation preserving reducibility that, as usual, can be applied both for inferring inapproximability results and for deriving new approximation algorithms.
The last two chapters extend the subject of approximate solution of NP-hard optimization problems in two directions. On one direction, Chap. 9 provides techniques and results for analyzing the expected performance of approximation algorithms. Such performance, which may often be substantially better than the worst case performance analyzed in the previous chapters, is determined by comparing, in probabilistic terms, the quality of the solution achieved by the algorithms with the expected value of the optimum solutions of the given combinatorial problem. On the other direction, Chap. 10 is intended to provide pointers to the literature concerning various popular techniques used in practice in the solution of discrete optimization problems. Despite the fact that they do not have guaranteed performance, such techniques may in practice behave quite well. Most of them are elaborated versions of local search (such in the case of tabu search, simulated annealing, and genetic algorithms). In other cases (i.e., branch and bound and branch and cut), they are based on classical operations research approaches.
One peculiar aspect of this book, that characterizes it at the same time as a text book and a reference book (similarly to [Garey and Johnson, 1979]) is the rich compendium containing information on approximability of more than 200 problems. The compendium is structured into twelve categories according to subject matter and, for each problem, it contains the best approximation positive result (i.e., the approximability upper bound) and the worst approximation negative result (i.e., the approximability lower bound) for the problem. Besides, each problem entry includes a section of additional comments where approximability results for variations of the problem are mentioned. Finally, a reference to the closest problem appearing in the list published in Garey and Johnson's book is given (whenever it is possible).
Each chapter contains several exercises which range from easy to very difficult ones: the degree of difficulty of an exercise is represented by the number of stars in front of it. Finally, the book is supplemented with an extensive bibliography with cross reference towards the compendium entries.
The book assumes that the reader is familiar with basic notions of (a) design and analysis of computer algorithms, (b) discrete mathematics, and (c) linear programming. However, for sake of completeness, the material presented in the various chapters is supplemented by the content of an appendix that is devoted to basic mathematical concepts and notations and to essential notions of linear programming.
The reading of the material presented in the book may be organized along four main threads. The first reading thread regards the design and performance analysis of basic approximation algorithms (BAA) for NP-hard optimization problems and develops through Chaps. 1 to 4: it may be taught in a senior undergraduate course within a curriculum in computer science or in applied mathematics and operations research. The second thread regards advanced techniques for the design and analysis of approximation algorithms (AAA) and develops through Chaps. 5, 9 and 10 with Chaps. 3 and 4 as prerequisites. The third reading thread regards the theoretical study of basic notions of approximation complexity (BAC). It develops through Chaps. 1, 2, 3, and 6 and it is meant for a senior undergraduate audience in computer science and mathematics. Finally, the fourth thread is devoted to advanced concepts of approximation complexity and inapproximability results (AAC). It develops through Chaps. 6, 7, 8 and it is meant for a graduate audience in computer science and mathematics with the preceding material (at least Chap. 3) as a prerequisite. In the table below the above four reading threads are summarized.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
This book has benefited from the collaboration of several students and friends who helped us in making the presentation as clean and clear as possible. In particular, we want to thank Paola Alimonti, Gunnar Andersson, Andrea Clementi, Alberto Del Lungo, Gianluca Della Vedova, Lars Engebretsen, Guido Fiorino, Manica Govekar, Roberto Grossi, Stefano Leonardi, Alessandro Panconesi, Massimo Santini, Riccardo Silvestri, Luca Trevisan. An incredible amount of people supported the compilation of the compendium. The following list certainly may not cover all contributors and we apologize for all omissions: Christoph Albrecht, Edoardo Amaldi, Yossi Azar, Reuven Bar-Yehuda, Bo Chen, Pascal Cherrier, Janka Chlebikova, Keith Edwards, Igor Egorov, Uriel Feige, Michel Goemans, Joachim Gudmundsson, Magnús M. Halldórsson, Refael Hassin, Cor Hurkens, Arun Jagota, David Johnson, Marek Karpinski, Owen Kaser, Sanjeev Khanna, Samir Khuller, Jon Kleinberg, Goran Konjevod, Guy Kortsarz, Matthias Krause, Sven O. Krumke, Ming Li, B. Ma, Prabhu Manyem, Madhav Marathe, Tarcisio Maugeri, Petra Mutzel, Nagi Nahas, Claudio Nogueira de Menezes, Alessandro Panconesi, Dan Pehoushek, Erez Petrank, Jan Plesník, Yuval Rabani, Satish Rao, Eilon Reshef, Günter Rote, Jean-Pieree Seifert, Norbert Sensen, Hadas Shachnai, Martin Skutella, Roberto Solis-Oba, Arie Tamir, Rakesh Vohra, Jürgen Wirtgen, Gerhard Woeginger, Bang Ye Wu, Mihalis Yannakakis. The very nice drawing on the book cover was made by Nesestril and Naceradsky.
And above all, we wish to thank Angela, Anna, Linda, Paola, and Susanna for their patience, support, and encouragement.
Finally we wish to remember our beloved friend and colleague Marco Protasi, who died at the age of 48, without having the pleasure to see this work, to which he devoted a considerable effort in the recent years, completed.