1. RANDOM 1997: Bolognna, Italy

José D. P. Rolim (Ed.): Randomization and Approximation Techniques in Computer Science, International Workshop, RANDOM'97, Bolognna, Italy, July 11-12. 1997, Proceedings. Lecture Notes in Computer Science 1269 Springer 1997, ISBN 3-540-63248-4 BibTeX

@proceedings{DBLP:conf/random/1997,
  editor    = {Jos{\'e} D. P. Rolim},
  title     = {Randomization and Approximation Techniques in Computer Science,
               International Workshop, RANDOM'97, Bolognna, Italy, July 11-12.
               1997, Proceedings},
  booktitle = {RANDOM},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1269},
  year      = {1997},
  isbn      = {3-540-63248-4},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talk

Marek Karpinski: Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. 1-14 BibTeX

Approximation

Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe: Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model. 15-26 BibTeX
Christos Levcopoulos, Joachim Gudmundsson: Approximation Algorithms for Covering Polygons with Squares and Similar Problems. 27-41 BibTeX
Bernd Kreuter, Till Nierhoff: Greedily Approximating the r-independent Set and k-center Problems on Random Instances. 43-53 BibTeX

Invited Talk

Sanjeev Arora: Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. 55 BibTeX

Randomness

Prasad Tetali, Santosh Vempala: Random Sampling of Euler Tours. 57-66 BibTeX
Oded Goldreich, Shmuel Safra: A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. 67-84 BibTeX
Steven Rudich: Super-bits, Demi-bits, and NP/qpoly-natural Proofs. 85-93 BibTeX
Michael E. Saks, Shiyu Zhou: Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. 95-109 BibTeX

Invited Talk

Pierluigi Crescenzi, Viggo Kann: Approximation on the Web: A Compendium of NP Optimization Problems. 111-118 BibTeX

Algorithms

Andreas S. Schulz, Martin Skutella: Random-Based Scheduling: New Approximations and LP Lower Bounds. 119-133 BibTeX
Marcus Peinado, Thomas Lengauer: `Go with the winners' Generators with Applications to Molecular Modeling. 135-149 BibTeX
Dawei Hong, Jean-Camille Birget: Probabilistic Approximation of Some NP Optimization Problems by Finite-State Machines. 151-164 BibTeX

Invited Talk

Russell Impagliazzo: Using Hard Problems to Derandomize Algorithms: An Incomplete Survey. 165-173 BibTeX

Complexity

Andris Ambainis, Rusins Freivalds, Marek Karpinski: Weak and Strong Recognition by 2-way Randomized Automata. 175-185 BibTeX
Janis Kaneps, Dainis Geidmanis, Rusins Freivalds: Tally Languages Accepted by Monte Carlo Pushdown Automata. 187-195 BibTeX
Steven M. Kautz: Resource-Bounded Randomness and Compressibility with Respect to Nonuniform Measures. 197-211 BibTeX
Yongge Wang: Randomness, Stochasticity and Approximations. 213-225 BibTeX