Randomization and Approximation Techniques in Computer Science: International Workshop RANDOM’97 Bologna, Italy, July 11–12, 1997 Proceedings

Marek Karpinski (auth.), José Rolim (eds.)3540632484, 9783540632481

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.

---

Table of contents :
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems….Pages 1-14
Average-case complexity of shortest-paths problems in the vertex-potential model….Pages 15-26
Approximation algorithms for covering polygons with squares and similar problems….Pages 27-41
Greedily approximating the r -independent set and k -center problems on random instances….Pages 43-53
Nearly linear time approximation schemes for Euclidean TSP and other geometric problems….Pages 55-55
Random sampling of Euler tours….Pages 57-66
A combinatorial consistency lemma with application to proving the PCP theorem….Pages 67-84
Super-bits, demi-bits, and NP/qpoly -natural proofs….Pages 85-93
Sample spaces with small bias on neighborhoods and error-correcting communication protocols….Pages 95-109
Approximation on the web: A compendium of NP optimization problems….Pages 111-118
Random-based scheduling new approximations and LP lower bounds….Pages 119-133
‘Go with the winners’ generators with applications to molecular modeling….Pages 135-149
Probabilistic approximation of some NP optimization problems by finite-state machines….Pages 151-164
Using hard problems to derandomize algorithms: An incomplete survey….Pages 165-173
Weak and strong recognition by 2-way randomized automata….Pages 175-185
Tally languages accepted by Monte Carlo pushdown automata….Pages 187-195
Resource-bounded randomness and compressibility with respect to nonuniform measures….Pages 197-211
Randomness, stochasticity and approximations….Pages 213-225