Tools

LEADER 03481cam 2200385 a 4500

001 ocm37220997;

003 OCoLC;

005 20141212125324.0;

008 970623s1997 gw a b 101 0 eng ;

010 a| 97027556;

015 a| GB97-49277;

019 a| 37464857;

020 a| 3540632484 (softcover : alk. paper);

035 a| (Sirsi) o37220997;

035 a| (OCoLC)37220997;

049 a| EREE;

050 00 a| QA76b| .R266 1997;

082 00 a| 004/.01/51142| 21;

111 2 a| International Workshop on Randomization and Approximation Techniques in Computer Scienced| (1997 :c| Bologna, Italy)=| ^A683167;

245 10 a| Randomization and approximation techniques in computer science :b| international workshop RANDOM '97, Bologna, Italy, July 11-12, 1997 : proceedings /c| José Rolim, (ed.).;

300 a| viii, 225 pages :b| illustrations ;c| 24 cm.;

336 a| text2| rdacontent;

337 a| unmediated2| rdamedia;

338 a| volume2| rdacarrier;

490 1 a| Lecture notes in computer science ;v| 1269;

504 a| Includes bibliographical references and index.;

505 0 a| Polynomial time approximation schemes for some dense instances of NP-hard optimization problems / Marek Karpinski -- Average-case complexity of shortest-paths problems in the vertex-potential model / Colin Cooper ... [et al.] -- Approximation algorithms for covering polygons with squares and similar problems / Christos Levcopoulos and Joachim Gudmundsson -- Greedily approximating the r-independent set and k-center problems on random instances / Bernd Kreuter and Till Nierhoff -- Nearly linear time approximation schemes for Euclidean TSP and other geometric problems / Sanjeev Arora --Random sampling of Euler tours / Prasad Tetali and Santosh Vempala -- A combinatorial consistency lemma with application to proving the PCP theorem / Oded Goldreich and Shmuel Safra -- Super-bits, demi-bits, and NP̃/qpoly-natural proofs / Steven Rudich -- Sample spaces with small bias on neighborhoods and error-correcting communication protocols / Michael Saks and Shiyu Zhou -- Approximation on the Web : a compendium of NP optimization problems / Pierluigi Crescenzi and Viggo Kann -- Random-based scheduling : new approximations and LP lower bounds / Andreas S. Schulz and Martin Skutella --'Go with the winners' generators with applications to molecular modeling / Marcus Peinado and Thomas Lengauer -- Probabilistic approximation of some NP optimization problems by finite-state machines / Dawei Hong and Jean-Camille Birget -- Using hard problems to derandomize algorithms : an incomplete survey / Russell Impagliazzo -- Weak and strong recognition by 2-way randomized automata / Andris Ambainis, Rūsiņs̆ Freivalds and Marek Karpinski -- Tally languages accepted by Monte Carlo pushdown automata / Jānis Kaņeps, Dainis Geidmanis and Rūsiņs Freivalds -- Resources-bounded randomness and compressibility with respect to nonuniform measures / Steven M. Kautz -- Randomness, stochasticity, and approximations / Yongge Wang.;

650 0 a| Computer sciencex| Statistical methodsv| Congresses.=| ^A267953;

700 1 a| Rolim, José D. P.=| ^A373286;

830 0 a| Lecture notes in computer sciencev| 1269.=| ^A466336;

596 a| 1;

998 a| 629335;

999 a| QA76 .R266 1997w| LCc| 1i| 30372010018841d| 2/8/2013f| 2/8/2013g| 1l| JGESm| JOYNERr| Ys| Yt| JGESBKu| 4/21/1998x| BOOKz| JSTACKSo| .STAFF. 0;

Randomization and approximation techniques in computer science : international workshop RANDOM '97, Bologna, Italy, July 11-12, 1997 : proceedings / José Rolim, (ed.).

Author/creator	International Workshop on Randomization and Approximation Techniques in Computer Science
Other author	Rolim, José D. P.
Format	Book
Publication Info	Berlin ; New York : Springer, ©1997.
Description	viii, 225 pages : illustrations ; 24 cm.
Subjects	Computer science--Statistical methods. --Congresses.

Series	Lecture notes in computer science ; 1269 Lecture notes in computer science 1269. ^A466336
Contents	Polynomial time approximation schemes for some dense instances of NP-hard optimization problems / Marek Karpinski -- Average-case complexity of shortest-paths problems in the vertex-potential model / Colin Cooper ... [et al.] -- Approximation algorithms for covering polygons with squares and similar problems / Christos Levcopoulos and Joachim Gudmundsson -- Greedily approximating the r-independent set and k-center problems on random instances / Bernd Kreuter and Till Nierhoff -- Nearly linear time approximation schemes for Euclidean TSP and other geometric problems / Sanjeev Arora --Random sampling of Euler tours / Prasad Tetali and Santosh Vempala -- A combinatorial consistency lemma with application to proving the PCP theorem / Oded Goldreich and Shmuel Safra -- Super-bits, demi-bits, and NP̃/qpoly-natural proofs / Steven Rudich -- Sample spaces with small bias on neighborhoods and error-correcting communication protocols / Michael Saks and Shiyu Zhou -- Approximation on the Web : a compendium of NP optimization problems / Pierluigi Crescenzi and Viggo Kann -- Random-based scheduling : new approximations and LP lower bounds / Andreas S. Schulz and Martin Skutella --'Go with the winners' generators with applications to molecular modeling / Marcus Peinado and Thomas Lengauer -- Probabilistic approximation of some NP optimization problems by finite-state machines / Dawei Hong and Jean-Camille Birget -- Using hard problems to derandomize algorithms : an incomplete survey / Russell Impagliazzo -- Weak and strong recognition by 2-way randomized automata / Andris Ambainis, Rūsiņs̆ Freivalds and Marek Karpinski -- Tally languages accepted by Monte Carlo pushdown automata / Jānis Kaņeps, Dainis Geidmanis and Rūsiņs Freivalds -- Resources-bounded randomness and compressibility with respect to nonuniform measures / Steven M. Kautz -- Randomness, stochasticity, and approximations / Yongge Wang.
Bibliography note	Includes bibliographical references and index.
LCCN	97027556
ISBN	3540632484 (softcover : alk. paper)

Availability

Library	Location	Call Number	Status	Item Actions
Joyner	General Stacks	QA76 .R266 1997	✔ Available	Place Hold

Randomization and approximation techniques in computer science : international workshop RANDOM '97, Bologna, Italy, July 11-12, 1997 : proceedings / José Rolim, (ed.).

Click here for more information about this title

Availability