Lectures on proof verification and approximation algorithms
Proceedings of conferences of miscellaneous specific interest (00B25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)
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]
- On the approximation of the minimum disturbance \(p\)-facility location problem
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- Data science applications to string theory
- Approximation algorithms for the TSP with sharpened triangle inequality
- scientific article; zbMATH DE number 1304339 (Why is no real title available?)
- Deterministic and randomized polynomial‐time approximation of radii
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Verified Approximation Algorithms
- Partial digest is hard to solve for erroneous input data
This page was built for publication: Lectures on proof verification and approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1388145)
