Edición de la obra Lectures on proof verification and approximation algorithms
| Autor | Ernst Mayr, H. J. Prömel, Angelika Steger |
|---|---|
| Editorial | Springer |
| Fecha de publicación | 1998 |
| Lugar | Berlin, New York |
| Idioma | inglés |
| Páginas | 344 |
| Formato | [electronic resource] / |
| OCLC | 48936093 |
| 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.