Lectures on Proof Verification and Approximation Algorithms

Lectures on Proof Verification and Approximation Algorithms edited by Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger.

During the last few years, we have seen quite spectacular progress in the area of approximation algorithms: for several fundamental optimization problems we now actually know matching upper and lower bounds for their approximability. This textbook-like tutorial is a coherent and essentially self-con...

Full description

Saved in:
Bibliographic Details
Corporate Author: SpringerLink (Online service)
Other Authors: Mayr, Ernst W. (Editor), Prömel, Hans Jürgen (Editor), Steger, Angelika (Editor)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1998.
Edition:1st ed. 1998.
Series:Lecture Notes in Computer Science, 1367
Springer eBook Collection.
Subjects:
Computers.
Algorithms.
Computer science—Mathematics.
Combinatorics.
Calculus of variations.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • to the theory of complexity and approximation algorithms
  • to randomized algorithms
  • Derandomization
  • Proof checking and non-approximability
  • Proving the PCP-Theorem
  • Parallel repetition of MIP(2,1) systems
  • Bounds for approximating MaxLinEq3-2 and MaxEkSat
  • Deriving non-approximability results by reductions
  • Optimal non-approximability of MaxClique
  • The hardness of approximating set cover
  • Semidefinite programming and its applications to approximation algorithms
  • Dense instances of hard optimization problems
  • Polynomial time approximation schemes for geometric optimization problems in euclidean metric spaces.

Similar Items