Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 1998

Randomization and Approximation Techniques in Computer Science

Second International Workshop, RANDOM’98, Barcelona, Spain, October 8–10, 1998 Proceedings

Editors:

  1. Michael Luby

    1. International Computer Science Institute, Berkeley, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. José D. P. Rolim

    1. Computer Science Department, University of Geneva, Geneva 4, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Maria Serna

    1. University of Barcelona (UPC), Barcelona, Spain

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1518)

Conference series link(s): RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science

Conference proceedings info: RANDOM 1998.

Sections

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (29 papers)

  1. Front Matter

    Pages I-IX
    PDF

  3. Regular Papers

    1. A Derandomization Using Min-Wise Independent Permutations

      • Andrei Z. Broder, Moses Charikar, Michael Mitzenmacher
      Pages 15-24

    2. An Algorithmic Embedding of Graphs via Perfect Matchings

      • Vojtech Rödl, Andrzej Ruciński, Michelle Wagner
      Pages 25-34

    6. On-line Bin-Stretching

      • Yossi Azar, Oded Regev
      Pages 71-81

    9. Robotic Exploration, Brownian Motion and Electrical Resistance

      • Israel A. Wagner, Michael Lindenbaum, Alfred M. Bruckstein
      Pages 116-130

    10. Fringe analysis of synchronized parallel algorithms on 2–3 trees

      • R. Baeza-Yates, J. Gabarró, X. Messeguer
      Pages 131-144

    11. On Balls and Bins with Deletions

      • Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh Sitaraman et al.
      Pages 145-158

    12. “Balls into Bins” — A Simple and Tight Analysis

      • Martin Raab, Angelika Steger
      Pages 159-170

  5. Regular Papers

    1. Using Approximation Hardness to Achieve Dependable Computation

      • Mike Burmester, Yvo Desmedt, Yongge Wang
      Pages 172-186

    2. Complexity of Sequential Pattern Matching Algorithms

      • Mireille Régnier, Wojciech Szpankowski
      Pages 187-199

    3. A Random Server Model for Private Information Retrieval

      • Yael Gertner, Shafi Goldwasser, Tal Malkin
      Pages 200-217

    5. Randomized Lower Bounds for Online Path Coloring

      • Stefano Leonardi, Andrea Vitaletti
      Pages 232-247
Back to top

Other Volumes

  1. Randomization and Approximation Techniques in Computer Science

Back to top

Keywords

Back to top

Editors and Affiliations

  • International Computer Science Institute, Berkeley, USA

    Michael Luby

  • Computer Science Department, University of Geneva, Geneva 4, Switzerland

    José D. P. Rolim

  • University of Barcelona (UPC), Barcelona, Spain

    Maria Serna

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation