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...
সংরক্ষণ করুন:
| প্রধান লেখক: | |
|---|---|
| অন্যান্য লেখক: | , |
| বিন্যাস: | Livre numérique |
| ভাষা: | Anglais |
| প্রকাশিত: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| মালা: | Lecture notes in computer science
1367 |
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| টীকা: |
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 |
| LEADER | 03788nam a22004457a 4500 | ||
|---|---|---|---|
| 001 | 972840 | ||
| 008 | 110927q2000 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN155230883 | ||
| 020 | |a 9783540697015 (PDF) | ||
| 041 | 0 | |a eng | |
| 082 | |a 004 | ||
| 100 | 1 | |a Mayr, Ernst W., |d 1950- | |
| 245 | 1 | 0 | |a Lectures on proof verification and approximation algorithms |c [edited by] Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger. |
| 260 | |a Berlin [etc.] : |b Springer. | ||
| 260 | |a Cham : |b Springer Nature, |c [20..]. | ||
| 490 | 0 | |a Lecture notes in computer science |v 1367 |x 1611-3349 | |
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 505 | 0 | |a 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. | |
| 506 | |a Accès en ligne pour les établissements français bénéficiaires des licences nationales | ||
| 506 | |a Accès soumis à abonnement pour tout autre établissement | ||
| 506 | |a Conditions particulières de réutilisation pour les bénéficiaires des licences nationales. https://www.licencesnationales.fr/springer-nature-ebooks-contrat-licence-ln-2017 | ||
| 520 | |a 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. | ||
| 650 | |a Informatique | ||
| 650 | |a Algorithmes | ||
| 650 | |a Complexité de calcul (informatique) | ||
| 650 | |a Analyse numérique | ||
| 650 | |a Théorèmes |x Démonstration automatique | ||
| 650 | |a Approximation, Théorie de l' | ||
| 650 | |a Analyse combinatoire | ||
| 650 | |a Calcul des variations | ||
| 700 | 1 | |a Prömel, Hans Jürgen. |4 pbd | |
| 700 | 1 | |a Steger, Angelika, |d 1962- |4 pbd | |
| 776 | 0 | |0 03544777X |t Lectures on proof verification and approximation algorithms |f Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger (eds.) |d 1998 |c Berlin |n Springer |p 1 vol. (XII-344 p.) |s Lecture notes in computer science |z 3-540-64201-3 | |
| 776 | 0 | |t Lectures on Proof Verification and Approximation Algorithms |b Texte imprimé |z 9783662171806 | |
| 856 | 4 | |q PDF |u https://doi.org/10.1007/BFb0053010 |z Accès sur la plateforme de l'éditeur | |
| 856 | 4 | |u https://revue-sommaire.istex.fr/ark:/67375/8Q1-TBZ9B6X1-G |z Accès sur la plateforme Istex | |
| 856 | 4 | |5 452349901:750632437 |u https://ezproxy.univ-orleans.fr/login?url=https://doi.org/10.1007/BFb0053010 |z Accès Université d'Orléans | |
| 856 | 4 | |5 180339901:753988909 |u https://ezproxy.insa-cvl.fr/login?qurl=https://doi.org/10.1007/BFb0053010 |z Accès INSA CVL | |
| 997 | |0 972840 |1 Livre numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||