Lectures on Proof Verification and Approximation Algorithms

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

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1998
• Tongue: English
• Leaves: 337
• Series: Lecture Notes in Computer Science 1367
• Edition: 1
• Category: Library

✦ Synopsis

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

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computation by Abstract Devices; Combinatorics; Calculus of Variations and Optimal Control; Optimization; Numeric Computing