Skip to main content
SpringerLink
Log in
Book cover

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

  • Conference proceedings
  • © 1999

Overview

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)

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

Access this book

Log in via an institution
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

Licence this eBook for your library

Institutional subscriptions

Table of contents (28 papers)

  1. Front Matter

    Download chapter 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

    1. Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths

      • Noga Alon, Uri Arad, Yossi Azar
      Pages 16-27

    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. A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

      • Hans Kellerer
      Pages 51-62

  4. Session Approx 2

    1. Set Cover with Requirements and Costs Evolving over Time

      • Milena Mihail
      Pages 63-72

    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

    4. Improved Bounds for Sampling Contingency Tables

      • Ben Morris
      Pages 121-129

  6. Invited Talk

    1. Probabilistic and Deterministic Approximations of the Permanent

      • Avi Wigderson
      Pages 130-130

  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

Keywords

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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation