Lectures on Proof Verification and Approximation Algorithms

Thomas Jansen (auth.), Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.)3540642013, 9783540642015

During the last few years, we have seen quite spectacular progress in the area of approximation algorithms: for several fundamental optimization problems we now actually know matching upper and lower bounds for their approximability. This textbook-like tutorial is a coherent and essentially self-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and aproximation algorithms. The basic concepts, methods, and results are presented in a unified way to provide a smooth introduction for newcomers. These lectures are particularly useful for advanced courses or reading groups on the topic.

---

Table of contents :
Introduction to the theory of complexity and approximation algorithms….Pages 5-28
Introduction to randomized algorithms….Pages 29-39
Derandomization….Pages 41-61
Proof checking and non-approximability….Pages 63-82
Proving the PCP-Theorem….Pages 83-160
Parallel repetition of MIP(2,1) systems….Pages 161-177
Bounds for approximating MaxLinEq3-2 and MaxEkSat….Pages 179-211
Deriving non-approximability results by reductions….Pages 213-233
Optimal non-approximability of MaxClique….Pages 235-248
The hardness of approximating set cover….Pages 249-262
Semidefinite programming and its applications to approximation algorithms….Pages 263-298
Dense instances of hard optimization problems….Pages 299-311
Polynomial time approximation schemes for geometric optimization problems in euclidean metric spaces….Pages 313-323