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