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

Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques

Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99,Berkeley, CA, USA, August 8-11, 1999 Pro

Editors:

  1. Dorit S. Hochbaum

    1. Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institute for Computer Science, University of Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. José D. P. Rolim

    1. Centre Universitaire d’Informatique, Carouge, Geneva, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Alistair Sinclair

    1. Computer Science Division, University of California, Berkeley

    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 1671)

Conference series link(s): APPROX: International Workshop on Approximation Algorithms for Combinatorial Optimization, RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science

Conference proceedings info: APPROX 1999, RANDOM 1999.

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 (28 papers)

  1. Front Matter

    PDF

  2. Session Random 1

    1. Completeness and Robustness Properties of Min-Wise Independent Permutations

      • Andrei Z. Broder, Michael Mitzenmacher
      Pages 1-10

    2. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families

      • Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
      Pages 11-15

  3. Session Approx 1

    2. Approximating Minimum Manhattan Networks

      • Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan
      Pages 28-38

    3. Approximation of Multi-Color Discrepancy

      • Benjamin Doerr, Anand Srivastav
      Pages 39-50

  4. Session Approx 2

    2. Multicoloring Planar Graphs and Partial k-Trees

      • Magnús M. Halldórsson, Guy Kortsarz
      Pages 73-84

  5. Session: Random 2

    1. Testing the Diameter of Graphs

      • Michal Parnas, Dana Ron
      Pages 85-96

    2. Improved Testing Algorithms for Monotonicity

      • Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
      Pages 97-108

    3. Linear Consistency Testing

      • Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
      Pages 109-120

  6. Invited Talk

  7. Session Random 3

    1. Improved Derandomization of BPP Using a Hitting Set Generator

      • Oded Goldreich, Avi Wigderson
      Pages 131-137

    2. Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets

      • Andreas Baltz, Tomasz Schoen, Anand Srivastav
      Pages 138-143

  8. Session Approx 3

    1. Stochastic Machine Scheduling: Performance Guarantees for LP-Based Priority Policies

      • Rolf H. Möhring, Andreas S. Schulz, Marc Uetz
      Pages 144-155

    2. Efficient Redundant Assignments under Fault-Tolerance Constraints

      • Dimitris A. Fotakis, Paul G. Spirakis
      Pages 156-167

    3. Scheduling with Machine Cost

      • Csanád Imreh, John Noga
      Pages 168-176

    4. A Linear Time Approximation Scheme for the Job Shop Scheduling Problem

      • Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko
      Pages 177-188
Back to top

Other Volumes

  1. Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques

Back to top

Keywords

Back to top

Editors and Affiliations

  • Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley

    Dorit S. Hochbaum

  • Institute for Computer Science, University of Kiel, Kiel, Germany

    Klaus Jansen

  • Centre Universitaire d’Informatique, Carouge, Geneva, Switzerland

    José D. P. Rolim

  • Computer Science Division, University of California, Berkeley

    Alistair Sinclair

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