Randomization and Approximation Techniques in Computer Science International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings /

• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Άλλοι συγγραφείς: Rolim, Jose (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1997.
• Έκδοση: 1st ed. 1997.
• Σειρά: Lecture Notes in Computer Science, 1269
• Θέματα: Computers.; Algorithms.; Computer science-Mathematics.; Calculus of variations.; Combinatorics.; Mathematical statistics.; Theory of Computation.; Algorithm Analysis and Problem Complexity.; Discrete Mathematics in Computer Science.; Calculus of Variations and Optimal Control; Optimization.; Probability and Statistics in Computer Science.

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...

Πίνακας περιεχομένων:

• 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.