|
|
|
| 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 | ||