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

Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques

4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA,USA, August 18-20, 2001

Editors:

  1. Michel Goemans

    1. Department of Mathematics, Massachusetts Institute of Technology, MIT, Cambridge, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institute for Computer Science and Applied Mathematics, 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, Université de Genéve, Genéve 4, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Luca Trevisan

    1. Computer Science Division, University of California at Berkeley, Berkeley, USA

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

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 2001, RANDOM 2001.

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

  1. Front Matter

    Pages I-IX
    PDF

  3. Contributed Talks of APPROX

    3. Online Weighted Flow Time and Deadline Scheduling

      • Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Kirk R. Pruhs
      Pages 36-47

    4. An Online Algorithm for the Postman Problem with a Small Penalty

      • Piotr Berman, Junichiro Fukuyama
      Pages 48-54

    6. Approximation Schemes for Ordered Vector Packing Problems

      • Alberto Caprara, Hans Kellerer, Ulrich Pferschy
      Pages 63-75

    7. Incremental Codes

      • Yevgeniy Dodis, Shai Halevi
      Pages 75-90

    9. Approximation Algorithms for Budget-Constrained Auctions

      • Rahul Garg, Vijay Kumar, Vinayaka Pandit
      Pages 102-113

    10. Minimizing Average Completion of Dedicated Tasks and Interval Graphs

      • Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai
      Pages 114-126

    11. A Greedy Facility Location Algorithm Analyzed Using Dual Fitting

      • Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay Vazirani
      Pages 127-137

    12. 0.863-Approximation Algorithm for MAX DICUT

      • Shiro Matuura, Tomomi Matsui
      Pages 138-146

    14. Some Approximation Results for the Maximum Agreement Forest Problem

      • Estela Maris Rodrigues, Marie-France Sagot, Yoshiko Wakabayashi
      Pages 159-169
Back to top

Other Volumes

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

Back to top

About this book

This book constitutes the joint refereed proceedings of the 4th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2001 and of the 5th International Workshop on Ranomization and Approximation Techniques in Computer Science, RANDOM 2001, held in Berkeley, California, USA in August 2001. The 26 revised full papers presented were carefully reviewed and selected from a total of 54 submissions. Among the issues addressed are design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization, de-randomization, average-case analysis, approximation classes, randomized complexity theory, scheduling, routing, coloring, partitioning, packing, covering, computational geometry, network design, and applications in various fields.
Back to top

Keywords

Back to top

Editors and Affiliations

  • Department of Mathematics, Massachusetts Institute of Technology, MIT, Cambridge, USA

    Michel Goemans

  • Institute for Computer Science and Applied Mathematics, University of Kiel, Kiel, Germany

    Klaus Jansen

  • Centre Universitaire d’Informatique, Université de Genéve, Genéve 4, Switzerland

    José D. P. Rolim

  • Computer Science Division, University of California at Berkeley, Berkeley, USA

    Luca Trevisan

Back to top

Bibliographic Information

  • Book Title: Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques

  • Book Subtitle: 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA,USA, August 18-20, 2001

  • Editors: Michel Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan

  • Series Title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/3-540-44666-4

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 2001

  • Softcover ISBN: 978-3-540-42470-3Published: 03 August 2001

  • eBook ISBN: 978-3-540-44666-8Published: 15 May 2003

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition Number: 1

  • Number of Pages: IX, 296

  • Topics: Analysis, Programming Techniques, Discrete Mathematics, Algorithm Analysis and Problem Complexity, Numeric Computing, Combinatorics

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