Lectures on Proof Verification and Approximation Algorithms

Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger, Eds.

Lecture Notes in Computer Science Vol. 1367, Springer, 1998.

Preface
Prologue
Introduction
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.3	MAXEkSAT, MAXSAT and MAXLINEQ3-2
	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
	3.7	A PRAM Algorithm for MAXIMALINDEPENDENTSET
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.4	MAXCUT and MAXEkSAT
	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
Bibliography
Author Index
Subject Index
List of Contributors

Volker Heun, 1997-03-10