Edición de la obra Lectures on proof verification and approximation algorithms
| Autor | Ernst W. Mayr, Angelika Steger |
|---|---|
| Editorial | Springer |
| Fecha de publicación | 1998 |
| Lugar | Berlin, New York |
| Idioma | inglés |
| Páginas | 344 |
| ISBN-10 | 3540642013 |
| OCLC | 98014448, 38478582 |
| LCCN | 98014448 |
| Serie | Lecture notes in computer science, · 1367 |
| Número de Cutter | M474l |
|---|
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.