Lectures on proof verification and approximation algorithms / / Ernst W. Mayr, Hans Jurgen Promel, Angelika Steger (eds.)

• Pubblicazione: Berlin ; ; Heidelberg : , : Springer, , [1998]; ©1998
• Edizione: 1st ed. 1998.
• Descrizione fisica: 1 online resource (XII, 348 p.)
• Disciplina: 003.54
• Soggetto topico: Computer software; Information theory
• Persona (resp. second.): MayrErnst; PrömelH. J.; StegerAngelika
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: 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.
• Sommario/riassunto: 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.
• Titolo autorizzato: Lectures on proof verification and approximation algorithms
• ISBN: 3-540-69701-2
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996466136803316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture notes in computer science ; ; 1367.