Skip to main content
SpringerLink
Log in

Algorithms - ESA 2001

9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings

  • Conference proceedings
  • © 2001

Overview

Editors:
  1. Friedhelm Meyer Heide

    1. Department of Mathematics and Computer Science and Heinz Nixdorf Institute, Paderborn University, Paderborn, Germany

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

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

  1. Front Matter

    Pages I-XII
    Download chapter PDF

  3. Caching and Prefetching

    1. Strongly Competitive Algorithms for Caching with Pipelined Prefetching

      • Alexander Gaysinsky, Alon Itai, Hadas Shachnai
      Pages 49-61

    2. Duality between Prefetching and Queued Writing with Parallel Disks

      • David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
      Pages 62-73

  4. Online Algorithms

    1. Online Bin Coloring

      • Sven O. Krumke, Willem E. de Paepe, Jörg Rambau, Leen Stougie
      Pages 74-85

    2. A General Decomposition Theorem for the k-Server Problem

      • Steven S. Seiden
      Pages 86-97

    3. Buying a Constant Competitive Ratio for Paging

      • János Csirik, Csanád Imreh, John Noga, Steve S. Seiden, Gerhard J. Woeginger
      Pages 98-108

  5. Data Structures I

    1. Simple Minimal Perfect Hashing in Less Space

      • Martin Dietzfelbinger, Torben Hagerup
      Pages 109-120

    2. Cuckoo Hashing

      • Rasmus Pagh, Flemming Friche Rodler
      Pages 121-133

  6. Optimization and Approximation

    1. Coupling Variable Fixing Algorithms for the Automatic Recording Problem

      • Meinolf Sellmann, Torsten Fahle
      Pages 134-145

    2. Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints

      • Renaud Lepére, Denis Trystram, Gerhard J. Woeginger
      Pages 146-157

    3. On the Approximability of the Minimum Test Collection Problem

      • Bjarni V. Halldórsson, Magnús M. Halldórsson, R. Ravi
      Pages 158-169

  7. Sequences

    1. Finding Approximate Repetitions under Hamming Distance

      • Roman Kolpakov, Gregory Kucherov
      Pages 170-181

    2. SNPs Problems, Complexity, and Algorithms

      • Giuseppe Lancia, Vineet Bafna, Sorin Istrail, Ross Lippert, Russell Schwartz
      Pages 182-193

  8. Scheduling

    1. A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs

      • Eric Angel, Evripidis Bampis, Alexander Kononov
      Pages 194-205

    2. Grouping Techniques for Scheduling Problems: Simpler and Faster

      • Aleksei V. Fishkin, Klaus Jansen, Monaldo Mastrolilli
      Pages 206-217

    3. A 2-Approximation Algorithm for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times

      • Yoshiyuki Karuno, Hiroshi Nagamochi
      Pages 218-229

  9. Shortest Paths

    1. A Simple Shortest Path Algorithm with Linear Average Time

      • Andrew V. Goldberg
      Pages 230-241
Back to top

Keywords

About this book

This book constitutes the refereed proceedings of the 9th Annual European Symposium on Algorithms, ESA 2001, held in Aarhus, Denmark, in August 2001.
The 41 revised full papers presented together with three invited contributions were carefully reviewed and selected from 102 submissions. The papers are organized in topical sections on caching and prefetching, online algorithms, data structures, optimization and approximation, sequences, scheduling, shortest paths, geometry, distributed algorithms, graph algorithms, pricing, broadcasting and multicasting, graph labeling and graph drawing, and graphs.

Editors and Affiliations

  • Department of Mathematics and Computer Science and Heinz Nixdorf Institute, Paderborn University, Paderborn, Germany

    Friedhelm Meyer Heide

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation