Lectures on proof verification and approximation algorithms
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-con...
Shranjeno v:
| Glavni avtor: | |
|---|---|
| Drugi avtorji: | , |
| Format: | Livre numérique |
| Jezik: | Anglais |
| Izdano: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Serija: | Lecture notes in computer science
1367 |
| Teme: | |
| Online dostop: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Sporočilo: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Lectures on proof verification and approximation algorithms, Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.), 1998, Berlin, Springer, 1 vol. (XII-344 p.), Lecture notes in computer science, 3-540-64201-3 • Lectures on Proof Verification and Approximation Algorithms, Texte imprimé, 9783662171806 |
Kazalo:
- 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.