| 000 | 02714camuu2200445 a 4500 | |
| 001 | 000000882957 | |
| 005 | 20040604143356 | |
| 007 | cruun | |
| 008 | 980213s1998 gw a b 001 0 eng | |
| 010 | ▼a 98014448 | |
| 015 | ▼a GB98-26041 | |
| 019 | ▼a 39002690 | |
| 020 | ▼a 3540642013 (Berlin : alk. paper) | |
| 040 | ▼a DLC ▼c DLC ▼d PMC ▼d OCL ▼d OHX ▼d UKM ▼d UBA ▼d C$Q ▼d MUQ ▼d 211009 | |
| 049 | 1 | ▼l 121094988 ▼f 과학 |
| 050 | 0 0 | ▼a QA76.9.A96 ▼b L43 1998 |
| 072 | 7 | ▼a QA ▼2 lcco |
| 082 | 0 0 | ▼a 005.1/4 ▼2 21 |
| 090 | ▼a 005.14 ▼b L471 | |
| 245 | 0 0 | ▼a Lectures on proof verification and approximation algorithms / ▼c Ernst W. Mayr, Hans Ju<rgen Pro<mel, Angelika Steger (eds.). |
| 260 | ▼a Berlin ; ▼a New York : ▼b Springer, ▼c c1998. | |
| 300 | ▼a xii, 344 p. : ▼b ill. ; ▼c 24 cm. | |
| 440 | 0 | ▼a Lecture notes in computer science, ▼x 0302-9743 ; ▼v 1367 |
| 504 | ▼a Includes bibliographical references (p. [325]-334) and indexes. | |
| 505 | 0 | ▼a Introduction to the theory of complexity and approximation algorithms / Thomas Jansen -- Introduction to randomized algorithms / Artur Andrzejak -- Derandomization / Detlef Sieling -- Proof checking and non-approximability / Stefan Hougardy -- Proving the PCP-theorem / Volker Heun, Wolfgang Merkle, Ulrich Weigand -- Parallel repetition of MIP(2,1) systems / Clemens Gro<pl, Martin Skutella -- Bounds for approximating MAXLINEQ3-2 and MAXEkSAT / Sebastian Seibert, Thomas Wilke -- Deriving non-approximability results by reductions / Claus Rick, Hein Ro<hrig -- Optimal non-approximability of MAXCLIQUE / Martin Mundhenk, Anna Slobodova* -- The hardness of approximating set cover / Alexander Wolff -- Semidefinite programming and its applications to approximation algorithms / Thomas Hofmeister, Martin Hu<hne -- Dense instances of hard optimization problems / Katja Wolf -- Polynomial time approximation schemes for geometric optimization problems in Euclidean metric spaces / Richard Mayr, Annette Schelten. |
| 530 | ▼a Also available via the World Wide Web. | |
| 650 | 0 | ▼a Automatic theorem proving. |
| 650 | 0 | ▼a Computer algorithms. |
| 650 | 0 | ▼a Approximation theory. |
| 650 | 7 | ▼a Algoritmos e estruturas de dados ▼2 larpcal |
| 650 | 7 | ▼a Computabilidade e modelos de computacao ▼2 larpcal |
| 650 | 6 | ▼a Theoremes ▼x Demonstration automatique |
| 650 | 6 | ▼a Algorithmes |
| 650 | 6 | ▼a Approximation, Theorie de l' |
| 700 | 1 | ▼a Mayr, Ernst. |
| 700 | 1 | ▼a Promel, H. J. |
| 700 | 1 | ▼a Steger, Angelika. |
| 856 | 4 1 | ▼u http://link.springer-ny.com/link/service/series/0558/tocs/t1367.htm ▼z Restricted to Springer LINK subscribers |
| 938 | ▼a Otto Harrassowitz ▼b HARR ▼n har000573025 ▼c 82.00 DEM |
소장정보
| No. | 소장처 | 청구기호 | 등록번호 | 도서상태 | 반납예정일 | 예약 | 서비스 |
|---|---|---|---|---|---|---|---|
| No. 1 | 소장처 과학도서관/Sci-Info(2층서고)/ | 청구기호 005.14 L471 | 등록번호 121094988 | 도서상태 대출가능 | 반납예정일 | 예약 | 서비스 |
컨텐츠정보
책소개
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.
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.
정보제공 :
목차
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.
정보제공 :