![Lectures on Proof Verification and Approximation Algorithms [electronic resource] /](/search/themes/bootstrap3/images/libros.png)
Lectures on Proof Verification and Approximation Algorithms [electronic resource] /
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.
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Texto biblioteca |
| Language: | eng |
| Published: |
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer,
1998
|
| Subjects: | Computer science., Computers., Algorithms., Computer science, Calculus of variations., Combinatorics., Computer Science., Theory of Computation., Algorithm Analysis and Problem Complexity., Discrete Mathematics in Computer Science., Computation by Abstract Devices., Calculus of Variations and Optimal Control; Optimization., |
| Online Access: | http://dx.doi.org/10.1007/BFb0053010 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
KOHA-OAI-TEST:207956 |
|---|---|
| record_format |
koha |
| spelling |
KOHA-OAI-TEST:2079562018-07-30T23:38:42ZLectures on Proof Verification and Approximation Algorithms [electronic resource] / Mayr, Ernst W. editor. Jürgen Prömel, Hans. editor. Steger, Angelika. editor. SpringerLink (Online service) textBerlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer,1998.engDuring 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.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.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.Computer science.Computers.Algorithms.Computer scienceCalculus of variations.Combinatorics.Computer Science.Theory of Computation.Algorithm Analysis and Problem Complexity.Discrete Mathematics in Computer Science.Computation by Abstract Devices.Combinatorics.Calculus of Variations and Optimal Control; Optimization.Springer eBookshttp://dx.doi.org/10.1007/BFb0053010URN:ISBN:9783540697015 |
| institution |
COLPOS |
| collection |
Koha |
| country |
México |
| countrycode |
MX |
| component |
Bibliográfico |
| access |
En linea En linea |
| databasecode |
cat-colpos |
| tag |
biblioteca |
| region |
America del Norte |
| libraryname |
Departamento de documentación y biblioteca de COLPOS |
| language |
eng |
| topic |
Computer science. Computers. Algorithms. Computer science Calculus of variations. Combinatorics. Computer Science. Theory of Computation. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Computation by Abstract Devices. Combinatorics. Calculus of Variations and Optimal Control; Optimization. Computer science. Computers. Algorithms. Computer science Calculus of variations. Combinatorics. Computer Science. Theory of Computation. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Computation by Abstract Devices. Combinatorics. Calculus of Variations and Optimal Control; Optimization. |
| spellingShingle |
Computer science. Computers. Algorithms. Computer science Calculus of variations. Combinatorics. Computer Science. Theory of Computation. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Computation by Abstract Devices. Combinatorics. Calculus of Variations and Optimal Control; Optimization. Computer science. Computers. Algorithms. Computer science Calculus of variations. Combinatorics. Computer Science. Theory of Computation. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Computation by Abstract Devices. Combinatorics. Calculus of Variations and Optimal Control; Optimization. Mayr, Ernst W. editor. Jürgen Prömel, Hans. editor. Steger, Angelika. editor. SpringerLink (Online service) Lectures on Proof Verification and Approximation Algorithms [electronic resource] / |
| description |
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. |
| format |
Texto |
| topic_facet |
Computer science. Computers. Algorithms. Computer science Calculus of variations. Combinatorics. Computer Science. Theory of Computation. Algorithm Analysis and Problem Complexity. Discrete Mathematics in Computer Science. Computation by Abstract Devices. Combinatorics. Calculus of Variations and Optimal Control; Optimization. |
| author |
Mayr, Ernst W. editor. Jürgen Prömel, Hans. editor. Steger, Angelika. editor. SpringerLink (Online service) |
| author_facet |
Mayr, Ernst W. editor. Jürgen Prömel, Hans. editor. Steger, Angelika. editor. SpringerLink (Online service) |
| author_sort |
Mayr, Ernst W. editor. |
| title |
Lectures on Proof Verification and Approximation Algorithms [electronic resource] / |
| title_short |
Lectures on Proof Verification and Approximation Algorithms [electronic resource] / |
| title_full |
Lectures on Proof Verification and Approximation Algorithms [electronic resource] / |
| title_fullStr |
Lectures on Proof Verification and Approximation Algorithms [electronic resource] / |
| title_full_unstemmed |
Lectures on Proof Verification and Approximation Algorithms [electronic resource] / |
| title_sort |
lectures on proof verification and approximation algorithms [electronic resource] / |
| publisher |
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, |
| publishDate |
1998 |
| url |
http://dx.doi.org/10.1007/BFb0053010 |
| work_keys_str_mv |
AT mayrernstweditor lecturesonproofverificationandapproximationalgorithmselectronicresource AT jurgenpromelhanseditor lecturesonproofverificationandapproximationalgorithmselectronicresource AT stegerangelikaeditor lecturesonproofverificationandapproximationalgorithmselectronicresource AT springerlinkonlineservice lecturesonproofverificationandapproximationalgorithmselectronicresource |
| _version_ |
1756268456201682944 |