Lectures on proof verification and approximation algorithms / / Ernst W. Mayr, Hans Jurgen Promel, Angelika Steger (eds.) |
Edizione | [1st ed. 1998.] |
Pubbl/distr/stampa | Berlin ; ; Heidelberg : , : Springer, , [1998] |
Descrizione fisica | 1 online resource (XII, 348 p.) |
Disciplina | 003.54 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computer software
Information theory |
ISBN | 3-540-69701-2 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
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. |
Record Nr. | UNINA-9910143457403321 |
Berlin ; ; Heidelberg : , : Springer, , [1998] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Lectures on proof verification and approximation algorithms / / Ernst W. Mayr, Hans Jurgen Promel, Angelika Steger (eds.) |
Edizione | [1st ed. 1998.] |
Pubbl/distr/stampa | Berlin ; ; Heidelberg : , : Springer, , [1998] |
Descrizione fisica | 1 online resource (XII, 348 p.) |
Disciplina | 003.54 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computer software
Information theory |
ISBN | 3-540-69701-2 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
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. |
Record Nr. | UNISA-996466136803316 |
Berlin ; ; Heidelberg : , : Springer, , [1998] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|