Randomization and Approximation Techniques in Computer Science: Second International Workshop, RANDOM’98 Barcelona, Spain, October 8–10, 1998 Proceedings

Alan M. Frieze (auth.), Michael Luby, José D. P. Rolim, Maria Serna (eds.)354065142X, 9783540651420

This book constitutes the refereed proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM’98, held in Barcelona, Spain, in October 1998. The 26 revised full papers presented were carefully reviewed and selected for inclusion in the proceedings. Also included are three invited contributions. Among the topics addressed are graph computation, derandomization, pattern matching, computational geometry, approximation algorithms, search algorithms, sorting, and networking algorithms.

---

Table of contents :
Disjoint Paths in Expander Graphs via Random Walks: a Short Survey….Pages 1-14
A Derandomization Using Min-Wise Independent Permutations….Pages 15-24
An Algorithmic Embedding of Graphs via Perfect Matchings….Pages 25-34
Deterministic Hypergraph Coloring and Its Applications….Pages 35-46
On the Derandomization of Space-Bounded Computations….Pages 47-59
Talagrand’s Inequality and Locality in Distributed Computing….Pages 60-70
On-line Bin-Stretching….Pages 71-81
Combinatorial Linear Programming: Geometry Can Help….Pages 82-96
A Note on Bounding the Mixing Time by Linear Programming….Pages 97-115
Robotic Exploration, Brownian Motion and Electrical Resistance….Pages 116-130
Fringe analysis of synchronized parallel algorithms on 2–3 trees….Pages 131-144
On Balls and Bins with Deletions….Pages 145-158
“Balls into Bins” — A Simple and Tight Analysis….Pages 159-170
Tornado Codes: Practical Erasure Codes Based on Random Irregular Graphs….Pages 171-171
Using Approximation Hardness to Achieve Dependable Computation….Pages 172-186
Complexity of Sequential Pattern Matching Algorithms….Pages 187-199
A Random Server Model for Private Information Retrieval….Pages 200-217
Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract)….Pages 218-231
Randomized Lower Bounds for Online Path Coloring….Pages 232-247
Parallel Random Search and Tabu Search for the Minimal Consistent Subset Selection Problem….Pages 248-259
On Various Cooling Schedules for Simulated Annealing Applied to the Job Shop Problem….Pages 260-279
A High Performance Approximate Algorithm for the Steiner Problem in Graphs….Pages 280-293
Random Geometric Problems on [0, 1] 2 ….Pages 294-306
A Role of Constraint in Self-Organization….Pages 307-318
Constructive Bounds and Exact Expectations for the Random Assignment Problem….Pages 319-330
The “Burnside Process” Converges Slowly….Pages 331-345
Quicksort Again Revisited….Pages 346-356
Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems….Pages 357-368
Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow….Pages 369-384