Lectures on proof verification and approximation algorithms. (English) Zbl 1043.68579

Lecture Notes in Computer Science 1367. Berlin: Springer (ISBN 3-540-64201-3/pbk). xii, 344 p. (1998).

Show indexed articles as search result.

The articles of this volume will be announced individually.
Indexed articles:
Jansen, Thomas, Introduction to the theory of complexity and approximation algorithms, 5-28 [Zbl 1401.68077]
Andrzejak, Artur, Introduction to randomized algorithms, 29-39 [Zbl 1401.68357]
Sieling, Detlef, Derandomization, 41-61 [Zbl 1401.68358]
Hougardy, Stefan, Proof checking and non-approximability, 63-82 [Zbl 1401.68091]
Heun, Volker; Merkle, Wolfgang; Weigand, Ulrich, Proving the PCP-theorem, 83-160 [Zbl 1401.68090]
Gröpl, Clemens; Skutella, Martin, Parallel repetition of \(\mathrm{MIP}(2,1)\) systems, 161-177 [Zbl 1401.68089]
Seibert, Sebastian; Wilke, Thomas, Bounds for approximating MaxLinEq3-2 and MaxE\(k\)Sat, 179-211 [Zbl 1401.68102]
Rick, Claus; Röhrig, Hein, Deriving non-approximability results by reductions, 213-233 [Zbl 1401.68101]
Mundhenk, Martin; Slobodová, Anna, Optimal non-approximability of MaxClique, 235-248 [Zbl 1401.68099]
Wolff, Alexander, The hardness of approximating set cover, 249-262 [Zbl 1401.68103]
Hofmeister, Thomas; Hühne, Martin, Semidefinite programming and its applications to approximation algorithms, 263-298 [Zbl 1401.68362]
Wolf, Katja, Dense instances of hard optimization problems, 299-311 [Zbl 1401.68364]
Mayr, Richard; Schelten, Annette, Polynomial time approximation schemes for geometric optimization problems in Euclidean metric spaces, 313-323 [Zbl 1401.68363]

MSC:

68W25	Approximation algorithms
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25	Analysis of algorithms and problem complexity
68-06	Proceedings, conferences, collections, etc. pertaining to computer science
00B25	Proceedings of conferences of miscellaneous specific interest