03931nam 22008175 450 991014345740332120250731082458.03-540-69701-210.1007/BFb0053010(CKB)1000000000210899(SSID)ssj0000324387(PQKBManifestationID)11286811(PQKBTitleCode)TC0000324387(PQKBWorkID)10313628(PQKB)10475077(DE-He213)978-3-540-69701-5(MiAaPQ)EBC5595773(MiAaPQ)EBC6485425(Au-PeEL)EBL5595773(OCoLC)1076252580(PPN)155230883(EXLCZ)99100000000021089920121227d1998 u| 0engurnn|008mamaatxtccrLectures on Proof Verification and Approximation Algorithms /edited by Ernst W. Mayr, Hans Jürgen Prömel, Angelika Steger1st ed. 1998.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,1998.1 online resource (XII, 348 p.) Lecture Notes in Computer Science,1611-3349 ;1367Bibliographic Level Mode of Issuance: Monograph3-540-64201-3 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.Lecture Notes in Computer Science,1611-3349 ;1367Computer scienceAlgorithmsComputer scienceMathematicsDiscrete mathematicsMathematical optimizationCalculus of variationsTheory of ComputationAlgorithmsDiscrete Mathematics in Computer ScienceDiscrete MathematicsCalculus of Variations and OptimizationComputer science.Algorithms.Computer scienceMathematics.Discrete mathematics.Mathematical optimization.Calculus of variations.Theory of Computation.Algorithms.Discrete Mathematics in Computer Science.Discrete Mathematics.Calculus of Variations and Optimization.003.54Mayr ErnstPromel H. J.Steger AngelikaMiAaPQMiAaPQMiAaPQBOOK9910143457403321Lectures on proof verification and approximation algorithms2105503UNINA