LEADER 05188nam  22007455  450 
001 996465753303316
005 20200704191231.0
010   $a3-540-69247-9
024 7 $a10.1007/3-540-63248-4
035   $a(CKB)1000000000234674
035   $a(SSID)ssj0000326086
035   $a(PQKBManifestationID)11254429
035   $a(PQKBTitleCode)TC0000326086
035   $a(PQKBWorkID)10265253
035   $a(PQKB)10657775
035   $a(DE-He213)978-3-540-69247-8
035   $a(PPN)155168924
035   $a(EXLCZ)991000000000234674
100   $a20121227d1997      u|             0
101 0 $aeng
135   $aurnn#008mamaa
181   $ctxt
182   $cc
183   $acr
200 10$aRandomization and Approximation Techniques in Computer Science$b[electronic resource] $eInternational Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings /$fedited by Jose Rolim
205   $a1st ed. 1997.
210  1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1997.
215   $a1 online resource (VIII, 236 p.)
225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v1269
300   $aBibliographic Level Mode of Issuance: Monograph
311   $a3-540-63248-4 
327   $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.
330   $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.
410  0$aLecture Notes in Computer Science,$x0302-9743 ;$v1269
606   $aComputers
606   $aAlgorithms
606   $aComputer science?Mathematics
606   $aCalculus of variations
606   $aCombinatorics
606   $aMathematical statistics
606   $aTheory of Computation$3https://scigraph.springernature.com/ontologies/product-market-codes/I16005
606   $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021
606   $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028
606   $aCalculus of Variations and Optimal Control; Optimization$3https://scigraph.springernature.com/ontologies/product-market-codes/M26016
606   $aCombinatorics$3https://scigraph.springernature.com/ontologies/product-market-codes/M29010
606   $aProbability and Statistics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17036
615  0$aComputers.
615  0$aAlgorithms.
615  0$aComputer science?Mathematics.
615  0$aCalculus of variations.
615  0$aCombinatorics.
615  0$aMathematical statistics.
615 14$aTheory of Computation.
615 24$aAlgorithm Analysis and Problem Complexity.
615 24$aDiscrete Mathematics in Computer Science.
615 24$aCalculus of Variations and Optimal Control; Optimization.
615 24$aCombinatorics.
615 24$aProbability and Statistics in Computer Science.
676   $a004/.01/5114
702   $aRolim$b Jose$4edt$4http://id.loc.gov/vocabulary/relators/edt
712 12$aWorkshop on Randomization and Approximation Techniques in Computer Science$f(1997 :$eBologna, Italy)
906   $aBOOK
912   $a996465753303316
996   $aRandomization and Approximation Techniques in Computer Science$92072177
997   $aUNISA