Randomization and Approximation Techniques in Computer Science

1. Front Matter

   PDF

2. Polynomial time approximation schemes for some dense instances of NP-hard optimization problems

   • Marek Karpinski

   Pages 1-14

3. Average-case complexity of shortest-paths problems in the vertex-potential model

   • Colin Cooper, Alan Frieze, Kurt Mehlhorn, Volker Priebe

   Pages 15-26

4. Approximation algorithms for covering polygons with squares and similar problems

   • Christos Levcopoulos, Joachim Gudmundsson

   Pages 27-41

5. Greedily approximating the r-independent set and k-center problems on random instances

   • Bernd Kreuter, Till Nierhoff

   Pages 43-53

6. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

   • Sanjeev Arora

   Pages 55-55

7. Random sampling of Euler tours

   • Prasad Tetali, Santosh Vempala

   Pages 57-66

8. A combinatorial consistency lemma with application to proving the PCP theorem

   • Oded Goldreich, Shmuel Safra

   Pages 67-84

9. Super-bits, demi-bits, and NP/qpoly-natural proofs

   • Steven Rudich

   Pages 85-93

10. Sample spaces with small bias on neighborhoods and error-correcting communication protocols

    • Michael Saks, Shiyu Zhou

    Pages 95-109

11. Approximation on the web: A compendium of NP optimization problems

    • P. Crescenzi, V. Kann

    Pages 111-118

12. Random-based scheduling new approximations and LP lower bounds

    • Andreas S. Schulz, Martin Skutella

    Pages 119-133

13. ‘Go with the winners’ generators with applications to molecular modeling

    • Marcus Peinado, Thomas Lengauer

    Pages 135-149

14. Probabilistic approximation of some NP optimization problems by finite-state machines

    • Dawei Hong, Jean-Camille Birget

    Pages 151-164

15. Using hard problems to derandomize algorithms: An incomplete survey

    • Russell Impagliazzo

    Pages 165-173

16. Weak and strong recognition by 2-way randomized automata

    • Andris Ambainis, Rūsiņš Freivalds, Marek Karpinski

    Pages 175-185

17. Tally languages accepted by Monte Carlo pushdown automata

    • Jānis Kaņeps, Dainis Geidmanis, Rūsiņš Freivalds

    Pages 187-195

18. Resource-bounded randomness and compressibility with respect to nonuniform measures

    • Steven M. Kautz

    Pages 197-211

19. Randomness, stochasticity and approximations

    • Yongge Wang

    Pages 213-225

20. Back Matter

    PDF

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.

• Approximation Algorithms
• Combinatorial Computation
• Complexity
• Computer
• Randomization
• Randomized Computation
• algorithm
• algorithms
• automata
• computer science
• modeling
• optimization
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics