ENGLISH

Lectures on Proof Verification and Approximation Algorithms

By Ernst W. Mayr , Thomas Jansen (auth.) , Hans Jürgen Prömel , Angelika Steger (eds.)

Book information

Publisher
Springer-Verlag Berlin Heidelberg
Year
1998
ISBN
3540642013, 9783540642015
DOI
10.1007/BFb0053010
LCC
QA76.9.A96 L43 1998
Open Library ID
OL354706M
Language
english
Format
PDF
Filesize
16 MB (16868029 bytes)
Series
Lecture Notes in Computer Science 1367
Edition
1
Pages
348\337
Library
Kolxo3
Time added
2010-02-05 01:51:52
Algorithm Analysis and Problem Complexity; Discret

Description

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.

Similar books