Dagstuhl Seminar Proof Verification and Approximation Algorithms 1997

Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (Eds.): Lectures on Proof Verification and Approximation Algorithms. (the book grow out of a Dagstuhl Seminar, April 21-25, 1997). Lecture Notes in Computer Science 1367 Springer 1998, ISBN 3-540-64201-3

Thomas Jansen:
Introduction to the Theory of Complexity and Approximation Algorithms. 5-28
Artur Andrzejak:
Introduction to Randomized Algorithms. 29-40
Detlef Sieling:
Derandomization. 41-62
Stefan Hougardy:
Proof Checking and Non-approximability. 63-82
Volker Heun, Wolfgang Merkle, Ulrich Weigand:
Proving the PCP-Theorem. 83-160
Clemens Gröpl, Martin Skutella:
Parallel Repetition of MIP(2, 1) Systems. 161-178
Sebastian Seibert, Thomas Wilke:
Bounds for Approximating MAXLINEQ3-2 and MAXEKSAT. 179-212
Claus Rick, Hein Röhrig:
Deriving Non-approximability Results by Reductions. 213-234
Martin Mundhenk, Anna Slobodová:
Optimal Non-approximability of MAXCLIQUE. 235-248
Alexander Wolff:
The Hardness of Approximating Set Cover. 249-262
Thomas Hofmeister, Martin Hühne:
Semidefinite Programming and Its Applications to Approximation Algorithms. 263-298
Katja Wolf:
Dense Instances of Hard Optimization Problems. 299-312
Richard Mayr, Annette Schelten:
Polynomial Time Approximation Schemes for Geometric Optimization Problems in Euclidean Metric Spaces. 313-324

Last update Wed Feb 15 04:02:11 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page