Lectures on Proof Verification and Approximation Algorithms by Ernst W. MayrLectures on Proof Verification and Approximation Algorithms by Ernst W. Mayr

Lectures on Proof Verification and Approximation Algorithms

byErnst W. MayrEditorHans Jürgen Prömel, Angelika Steger

Paperback | February 25, 1998

Pricing and Purchase Info

$82.61 online 
$96.95 list price save 14%
Earn 413 plum® points

Prices and offers may vary in store

Quantity:

In stock online

Ships free on orders over $25

Not available in stores

about

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-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and aproximation algorithms. The basic concepts, methods, and results are presented in a unified way to provide a smooth introduction for newcomers. These lectures are particularly useful for advanced courses or reading groups on the topic.
Title:Lectures on Proof Verification and Approximation AlgorithmsFormat:PaperbackDimensions:348 pages, 23.5 × 15.5 × 0.17 inPublished:February 25, 1998Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:3540642013

ISBN - 13:9783540642015

Reviews

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.

From Our Editors

During the last few years, spectacular progress occurred in the area of approximation algorithms: for several fundamental optimization problems we now know matching upper and lower bounds for their approximability. Lectures on Proof Verification and Approximation Algorithms is a coherent, self-contained presentation of recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and approximation algorithms. The basic concepts, methods, and results are together to provide a smooth introduction for newcomers to the field.