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

An on-line version of this book is available by Springer!

Lectures on Proof Verification and Approximation Algorithms

Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger, Eds.
LNCS 1367
Lecture Notes in Computer Science Vol. 1367, Springer, 1998.


1. Complexity and Approximation
Thomas Jansen
1.1 Introduction
1.2 Basic Definitions
1.3 Complexity Classes for Randomized Algorithms
1.4 Optimization and Approximation

2. Randomized Algorithms
Artur Andrzejak
2.1 Introduction
2.2 Las Vegas and Monte Carlo Algorithms
2.3 Examples of Randomized Algorithms
2.4 Randomized Rounding of Linear Programs
2.5 A Randomized Algorithm for MAXSAT

3. Derandomization
Detlef Sieling
3.1 Introduction
3.2 The Method of Conditional Probabilities
3.4 Approximation Algorithms for Linear Integer Programs
3.5 Reduction of the Size of the Probability Space
3.6 Another Approximation Algorithm for MAXE3SAT

4. Proof Checking and Non-Approximability
Stefan Hougardy
4.1 Introduction
4.2 Probabilistically Checkable Proofs
4.3 PCP and Non-Approximability
4.4 Non-Approximability of APX-Complete Problems
4.5 Expanders and the Hardness of Approximating MAXE3SAT-b
4.6 Non-Approximability of MAXCLIQUE
4.7 Improved Non-Approximability Results for MAXCLIQUE

5. Proving the PCP-Theorem
Volker Heun, Wolfgang Merkle, Ulrich Weigand
5.1 Introduction and Overview
5.2 Extended and Constant Verifiers
5.3 Encodings
5.4 Efficient Solution Verifiers
5.5 Composing Verifiers and the PCP-Theorem
5.6 The LFKN Test
5.7 The Low Degree Test
5.8 A Proof of Cook's Theorem

6. Parallel Repetition of MIP(2,1) Systems
Clemens Gröpl, Martin Skutella
6.1 Prologue
6.2 Introduction
6.3 Two-Prover One-Round Proof Systems
6.4 Reducing the Error Probability
6.5 Coordinate Games
6.6 How to Prove the Parallel Repetition Theorem (I)
6.7 How to Prove the Parallel Repetition Theorem (II)

7. Bounds for Approximating MAXLINEG3-2 and MAXEkSAT
Sebastian Seibert, Thomas Wilke
7.1 Introduction
7.2 Overall Structure of the Proofs
7.3 Long Code, Basic Tests, and Fourier Transform
7.4 Using the Parallel Repetition Theorem for Showing Satisfiability
7.5 An Optimal Lower Bound for Approximating MAXLINEQ3-2
7.6 Optimal Lower Bounds for Approximating MAXEkSAT

8. Deriving Non-Approximability Results by Reductions
Claus Rick, Hein Röhrig
8.1 Introduction
8.2 Constraint Satisfaction Problems
8.3 The Quality of Gadgets
8.4 Weighted vs. Unweighted Problems
8.5 Gadget Construction
8.6 Improved Results

9. Optimal Non-Approximability of MAXCLIQUE
Martin Mundhenk, Anna Slobodová
9.1 Introduction
9.2 A PCP-System for ROBE3SAT and Its Parallel Repetition
9.3 The Long Code and Its Complete Test
9.4 The Non-Approximability of MAXCLIQUE

10. The Hardness of Approximating Set Cover
Alexander Wolff
10.1 Introduction
10.2 The Multi-Prover Proof System
10.3 Construction of a Partition System
10.4 Reduction to Set Cover

11. Semidefinite Programming
Thomas Hofmeister, Martin Hühne
11.1 Introduction
11.2 Basics from Matrix Theory
11.3 Semidefinite Programming
11.4 Duality and an Interior-Point Method
11.5 Approximation Algorithms for MAXCUT
11.6 Modeling Asymmetric Problems
11.7 Combining Approximation Algorithms
11.8 Improving the Approximation Ratio
11.9 Modeling Maximum Independent Set as a Semidefinite Program ?

12. Dense Instances of Hard Optimization Problems
Katja Wolf
12.1 Introduction
12.2 Motivation and Preliminaries
12.3 Approximating Smooth Integer Programs
12.5 Related Work

13. Approximation Schemes for Geometric Problems
Richard Mayr, Annette Schelten
13.1 Introduction
13.2 Definitions and Notations
13.3 The Structure Theorem and Its Proof
13.4 The Algorithm
13.5 Applications to Some Related Problems
13.6 The Earlier PTAS

Author Index
Subject Index
List of Contributors

Volker Heun, 1997-03-10