Lectures on Proof Verification and Approximation Algorithms
Editors: Mayr, Ernst W., Prömel, Hans Jürgen, Steger, Angelika (Eds.)
Free PreviewBuy this book
- About this Textbook
-
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.
- Table of contents (13 chapters)
-
-
Introduction to the theory of complexity and approximation algorithms
Pages 5-28
-
Introduction to randomized algorithms
Pages 29-39
-
Derandomization
Pages 41-61
-
Proof checking and non-approximability
Pages 63-82
-
Proving the PCP-Theorem
Pages 83-160
-
Table of contents (13 chapters)
- Download Table of contents TXT (4.6 KB)
- Download Sample pages 1 PDF (106.1 KB)
- Download Table of contents PDF (73.2 KB)
Recommended for you
Bibliographic Information
- Bibliographic Information
-
- Book Title
- Lectures on Proof Verification and Approximation Algorithms
- Editors
-
- Ernst W. Mayr
- Hans Jürgen Prömel
- Angelika Steger
- Series Title
- Lecture Notes in Computer Science
- Series Volume
- 1367
- Copyright
- 1998
- Publisher
- Springer-Verlag Berlin Heidelberg
- Copyright Holder
- Springer-Verlag Berlin Heidelberg
- eBook ISBN
- 978-3-540-69701-5
- DOI
- 10.1007/BFb0053010
- Softcover ISBN
- 978-3-540-64201-5
- Series ISSN
- 0302-9743
- Edition Number
- 1
- Number of Pages
- XII, 348
- Topics
