2. RANDOM 1998: Barcelona, Spain

Michael Luby, José D. P. Rolim, Maria J. Serna (Eds.): Randomization and Approximation Techniques in Computer Science, Second International Workshop, RANDOM'98, Barcelona, Spain, October 8-10, 1998, Proceedings. Lecture Notes in Computer Science 1518 Springer 1998, ISBN 3-540-65142-X

Invited Paper

Alan M. Frieze:
Disjoint Paths in Expander Graphs via Random Walks: A Short Survey. 1-14

Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher:
A Derandomization Using Min-Wise Independent Permutations. 15-24
Vojtech Rödl, Andrzej Rucinski, Michelle Wagner:
An Algorithmic Embedding of Graphs via Perfect Matchings. 25-34
Chi-Jen Lu:
Deterministic Hypergraph Coloring and Its Applications. 35-46
Roy Armoni:
On the Derandomization of Space-Bounded Computations. 47-59
Devdatt P. Dubhashi:
Talagrand's Inequality and Locality in Distributed Computing. 60-70
Yossi Azar, Oded Regev:
On-Line Bin-Stretching. 71-81
Bernd Gärtner:
Combinatorial Linear Programming: Geometry Can Help. 82-96
Abraham Sharell:
A Note on Bounding the Mixing Time by Linear Programming. 97-115
Israel A. Wagner, Michael Lindenbaum, Alfred M. Bruckstein:
Robotic Exploration, Brownian Motion and Electrical Resistance. 116-130
Ricardo A. Baeza-Yates, Joaquim Gabarró, Xavier Messeguer:
Fringe Analysis of Synchronized Parallel Algorithms on 2-3 Trees. 131-144
Richard Cole, Alan M. Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh K. Sitaraman, Eli Upfal:
On Balls and Bins with Deletions. 145-158
Martin Raab, Angelika Steger:
"Balls into Bins" - A Simple and Tight Analysis. 159-170

Michael Luby:
Tornado Codes: Practical Erasure Codes Based on Random Irregular Graphs. 171

Mike Burmester, Yvo Desmedt, Yongge Wang:
Using Approximation Hardness to Achieve Dependable Computation. 172-186
Mireille Régnier, Wojciech Szpankowski:
Complexity of Sequential Pattern Matching Algorithms. 187-199
Yael Gertner, Shafi Goldwasser, Tal Malkin:
A Random Server Model for Private Information Retrieval or How to Achieve Information Theoretic PIR Avoiding Database Replication. 200-217
Claus-Peter Schnorr, C. R. Subramanian:
Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract). 218-231
Stefano Leonardi, Andrea Vitaletti:
Randomized Lower Bounds for Online Path Coloring. 232-247
Vicente Cerverón, Ariadna Fuertes:
Parallel Random Search and Tabu Search for the Minimal Consistent Subset Selection Problem. 248-259
Kathleen Steinhöfel, Andreas Alexander Albrecht, C. K. Wong:
On Various Cooling Schedules for Simulated Annealing Applied to the Job Shop Problem. 260-279
Pere Guitart, Josep M. Basart:
A High Performance Approximate Algorithm for the Steiner Problem in Graphs. 280-293

Josep Díaz, Jordi Petit, Maria J. Serna:
Random Geometric Problems on [0, 1]². 294-306

Carlos Domingo, Osamu Watanabe, Tadashi Yamazaki:
A Role of Constraint in Self-Organization. 307-318
Don Coppersmith, Gregory B. Sorkin:
Constructive Bounds and Exact Expectations for the Random Assignment Problem. 319-330
Leslie Ann Goldberg, Mark Jerrum:
The "Burnside Process" Converges Slowly. 331-345
Charles Knessl, Wojciech Szpankowski:
Quicksort Again Revisited. 345-356
Gunnar Andersson, Lars Engebretsen:
Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems. 357-368
S. Muthukrishnan, Torsten Suel:
Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow. 369-384

Last update Wed May 22 16:23:23 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page