04105nam a22006135i 4500
978-3-540-69247-8
DE-He213
20170515111448.0
cr nn 008mamaa
121227s1997 gw | s |||| 0|eng d
9783540692478
978-3-540-69247-8
10.1007/3-540-63248-4
doi
QA75.5-76.95
UY
bicssc
UYA
bicssc
COM014000
bisacsh
COM031000
bisacsh
004.0151
23
Randomization and Approximation Techniques in Computer Science
[electronic resource] :
International Workshop RANDOM'97 Bologna, Italy, July 11–12, 1997 Proceedings /
edited by José Rolim.
Berlin, Heidelberg :
Springer Berlin Heidelberg,
1997.
VIII, 236 p.
online resource.
text
txt
rdacontent
computer
c
rdamedia
online resource
cr
rdacarrier
text file
PDF
rda
Lecture Notes in Computer Science,
0302-9743 ;
1269
Polynomial 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.
This 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.
Computer science.
Computers.
Algorithms.
Computer science
Mathematics.
Mathematical statistics.
Calculus of variations.
Combinatorics.
Computer Science.
Theory of Computation.
Algorithm Analysis and Problem Complexity.
Discrete Mathematics in Computer Science.
Calculus of Variations and Optimal Control; Optimization.
Combinatorics.
Probability and Statistics in Computer Science.
Rolim, José.
editor.
SpringerLink (Online service)
Springer eBooks
Printed edition:
9783540632481
Lecture Notes in Computer Science,
0302-9743 ;
1269
http://dx.doi.org/10.1007/3-540-63248-4
ZDB-2-SCS
ZDB-2-LNC
ZDB-2-BAE
ddc
EB
Computer Science (Springer-11645)
14343
14343