04107nam a22006135i 4500001001800000003000900018005001700027007001500044008004100059020003700100024003100137050001700168072001500185072001600200072002300216072002300239082001700262245020000279264006100479300003500540336002600575337002600601338003600627347002400663490005800687505134600745520063402091650002202725650001502747650001602762650003502778650002902813650002802842650001902870650002202889650002702911650004702938650004602985650006203031650001903093650005203112700002803164710003403192773002003226776003603246830005803282856004403340912001403384912001403398912001403412942001203426950003803438999001703476978-3-540-69247-8DE-He21320170515111448.0cr nn 008mamaa121227s1997 gw | s |||| 0|eng d a97835406924789978-3-540-69247-87 a10.1007/3-540-63248-42doi 4aQA75.5-76.95 7aUY2bicssc 7aUYA2bicssc 7aCOM0140002bisacsh 7aCOM0310002bisacsh04a004.015122310aRandomization and Approximation Techniques in Computer Scienceh[electronic resource] :bInternational Workshop RANDOM'97 Bologna, Italy, July 11–12, 1997 Proceedings /cedited by José Rolim. 1aBerlin, Heidelberg :bSpringer Berlin Heidelberg,c1997. aVIII, 236 p.bonline resource. atextbtxt2rdacontent acomputerbc2rdamedia aonline resourcebcr2rdacarrier atext filebPDF2rda1 aLecture Notes in Computer Science,x0302-9743 ;v12690 aPolynomial time approximation schemes for some dense instances of NP-hard optimization problems -- Average-case complexity of shortest-paths problems in the vertex-potential model -- Approximation algorithms for covering polygons with squares and similar problems -- Greedily approximating the r-independent set and k-center problems on random instances -- Nearly linear time approximation schemes for Euclidean TSP and other geometric problems -- Random sampling of Euler tours -- A combinatorial consistency lemma with application to proving the PCP theorem -- Super-bits, demi-bits, and NP/qpoly-natural proofs -- Sample spaces with small bias on neighborhoods and error-correcting communication protocols -- Approximation on the web: A compendium of NP optimization problems -- Random-based scheduling new approximations and LP lower bounds -- ‘Go with the winners’ generators with applications to molecular modeling -- Probabilistic approximation of some NP optimization problems by finite-state machines -- Using hard problems to derandomize algorithms: An incomplete survey -- Weak and strong recognition by 2-way randomized automata -- Tally languages accepted by Monte Carlo pushdown automata -- Resource-bounded randomness and compressibility with respect to nonuniform measures -- Randomness, stochasticity and approximations. aThis book constitutes the refereed proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97, held as a satelite meeting of ICALP'97, in Bologna, Italy, in July 1997. The volume presents 14 thoroughly revised full papers selected from 37 submissions; also included are four invited contributions by leading researchers. The book focuses on algorithms and complexity aspects arising in the development of efficient randomized solutions to computationally difficult problems. The papers are organized in sections on approximation, randomness, algorithms, and complexity. 0aComputer science. 0aComputers. 0aAlgorithms. 0aComputer sciencexMathematics. 0aMathematical statistics. 0aCalculus of variations. 0aCombinatorics.14aComputer Science.24aTheory of Computation.24aAlgorithm Analysis and Problem Complexity.24aDiscrete Mathematics in Computer Science.24aCalculus of Variations and Optimal Control; Optimization.24aCombinatorics.24aProbability and Statistics in Computer Science.1 aRolim, José.eeditor.2 aSpringerLink (Online service)0 tSpringer eBooks08iPrinted edition:z9783540632481 0aLecture Notes in Computer Science,x0302-9743 ;v126940uhttp://dx.doi.org/10.1007/3-540-63248-4 aZDB-2-SCS aZDB-2-LNC aZDB-2-BAE 2ddccEB aComputer Science (Springer-11645) c14343d14343