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.

Bibliographic Information

Book Title: Randomization and Approximation Techniques in Computer Science
Book Subtitle: International Workshop RANDOM'97, Bologna, Italy, July 11-12, 1997 Proceedings
Editors: José Rolim
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/3-540-63248-4
Publisher: Springer Berlin, Heidelberg
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1997
Softcover ISBN: 978-3-540-63248-1Published: 25 June 1997
eBook ISBN: 978-3-540-69247-8Published: 02 July 2005
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: VIII, 236
Topics: 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

Publish with us

Policies and ethics

Randomization and Approximation Techniques in Computer Science

Overview

Access this book

Other ways to access

Table of contents (18 papers)

Front Matter

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

Back Matter

Other volumes