Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Proof Verification and Approximation Algorithms	Introduction

Introduction

Perhaps surprisingly, it turned out that for several of these problems, including the well-known MAX3SAT, SETCOVER, MAXCLIQUE, and CHROMATICNUMBER, rather simple and straightforward algorithms already yield the essentially best possible bound, at least under some widely believed assumptions from complexity theory. The missing step for tightening the gap between upper and lower bound was the improvement of the lower or non-approximability bound. Here the progress was initiated by a result in a seemingly unrelated area, namely a new characterization of the well-known complexity class NP. This result is due to Arora, Lund, Motwani, Sudan, and Szegedy and is based on so-called probabilistically checkable proofs. While already very surprising and certainly interesting by itself, this result has given rise to fairly general techniques for deriving non-approximability results, and it initiated a large amount of subsequent work.

On the other hand, as if this so-to-speak "negative" progress had inspired the research community, the last few years have also brought us considerable progress on the "positive" or algorithmic side. Perhaps the two most spectacular results in this category are the approximation of MAXCUT using semidefinite programming, by Goemans and Williamson, and the development of polynomial time approximation schemes for various geometric problems, obtained independently by Arora and Mitchell.

These notes give an essentially self-contained exposition of some of these new and exciting developments for the interplay between complexity theory and approximation algorithms. The concepts, methods and results are presented in a unified way that should provide a smooth introduction to newcomers. In particular, we expect these notes to be a useful basis for an advanced course or reading group on probabilistically checkable proofs and approximability.

Overview and Organization of this Book

The second chapter presents a short introduction to randomized algorithms, demonstrating their usefulness by showing that an essentially trivial randomized algorithm for MAXE3SAT (the version of MAX3SAT in which all clauses have exactly three literals) has expected performance ratio 8/7. Later on, in Chapter 7, this ratio will be seen to be essentially best possible, assuming P != NP.

Concluding the introductory part, the third chapter describes various facets and techniques of derandomization, a term coined for the process of turning randomized algorithms into deterministic ones. Amongst other things in this chapter it is shown that the algorithm for MAX3SAT is easily derandomized.

Chapters 4 to 10 are devoted to the concept of probabilistically checkable proofs and the implications for non-approximability. Chapter 4 introduces the so-called PCP-Theorem, a new characterization of NP in terms of probabilistically checkable proofs, and explains why and how they can be used to show non-approximability results. In particular, the nonexistence of polynomial time approximation schemes for APX-complete problems and the non-approximability of MAXCLIQUE are shown in detail. A complete and self-contained proof of the PCP-Theorem is presented in Chapter 5. Chapter 6 is devoted to the so-called Parallel Repetition Theorem of Raz [Raz95] which is used heavily in subsequent chapters.

At the 1997 STOC, Håstad [Hås97] presented an exciting paper showing that the simple algorithm of Chapter 2 for approximating MAXE3SAT is essentially best possible. Chapter 7 is devoted to this result of Håstad's. The chapter also introduces the concept of long codes and a method of analyzing these codes by means of discrete Fourier transforms. These tools will be reused later in Chapter 9.

Chapter 8 surveys the new reduction techniques for optimization problems using gadgets, a notion for the first time formally introduced within the framework of approximation algorithms by Bellare, Goldreich, and Sudan [BGS95].

MAXCLIQUE cannot be approximated up to a factor of n^1-e unless NP = ZPP. This result, also due to Håstad [Hås96b], is based on a version of the PCP-Theorem using so-called free bits. This concept, as well as Håstad's result, are described in Chapter 9.

As the final installment in this series of optimal non-approximability results, Chapter 10 presents the result of Feige [Fei96] stating that for SETCOVER the approximation factor of ln n achieved by a simple greedy algorithm is essentially best possible unless NP <= DTIME( n^{O( log log n)}).

The last three chapters of these notes, are devoted to new directions in the development of approximation algorithms. First, Chapter~11 surveys recent achievements in constructing approximation algorithms based on semidefinite programming. A generalization of linear programming, semidefinite programming had been studied before for some time and in various contexts. However, only a few years ago Goemans and Williamson [GW95] showed how to make use of it in order to provide good approximation algorithms for several optimization problems.

While the PCP-Theorem implied that no APX-complete problem can have a polynomial time approximation scheme unless NP=P, it is quite surprising that many such problems nevertheless do have such approximation schemes when restricted to in a certain sense dense instances. Chapter 12 exemplifies a very general approach for such dense instances, due to Arora, Karger, and Karpinski [AKK95a].

The final chapter then presents one of the highlights of the work on approximation algorithms during recent years. It is the development of polynomial time approximation schemes for geometrical problems like the Euclidean traveling salesman problem, independently by Arora [Aro96,Aro97] and Mitchell [Mit96].

Notations and Conventions

We have also tried to avoid phrases like "reconsidering the proof of Theorem x in Chapter y we see that it also shows that ...". Instead, we have attempted to prove all statements in the form in which they'll be needed later on. We hope that in this way we have been able to make the arguments easier to follow and to improve readability of the text.

Finally, we want to explicitly add some disclaimers and an apology. The intention of these notes certainly is not to present a survey, detailed or not, on the history of research in proof verification or approximation algorithms. This means in particular, that more often than not only the reference to a paper with the best bound or complexity is given, omitting an entire sequence of earlier work without which the final result would appear all but impossible. Of course, numerous citations and pointers to work that had a major impact in the field are given, but there are doubtlessly many omissions and erroneous judgments. We therefore would like to apologize to all those whose work does not receive proper credit in these notes.

Acknowledgments