Algorithm Engineering

1. Front Matter

   Pages I-VIII

   PDF

2. Invited Lectures

   1. On the Differences between “Practical” and “Applied”

      • Karsten Weihe

      Pages 1-10

3. Contributed Papers

   1. An Experimental Study of Online Scheduling Algorithms

      • Susanne Albers, Bianca Schröder

      Pages 11-22

   2. Implementation of O(nmlog n) Weighted Matchings in General Graphs. The Power of Data Structures

      • Kurt Mehlhorn, Guido Schäfer

      Pages 23-38

   3. Pushing the Limits in Sequential Sorting

      • Stefan Edelkamp, Patrick Stiegeler

      Pages 39-50

   4. Efficient Sorting Using Registers and Caches

      • Lars Arge, Jeff Chase, Jeffrey S. Vitter, Rajiv Wickremesinghe

      Pages 51-62

   5. Lattice Basis Reduction with Dynamic Approximation

      • Werner Backes, Susanne Wetzel

      Pages 63-73

   6. Clustering Data without Prior Knowledge

      • Javed Aslam, Alain Leblanc, Clifford Stein

      Pages 74-86

   7. Recognizing Bundles in Time Table Graphs - A Structural Approach

      • Annegret Liebers, Karsten Weihe

      Pages 87-98

   8. Analysis and Experimental Evaluation of an Innovative and Efficient Routing Protocol for Ad-hoc Mobile Networks

      • I. Chatzigiannakis, S. Nikoletseas, P. Spirakis

      Pages 99-110

   9. Portable List Ranking: An Experimental Study

      • Isabelle Guérin Lassous, Jens Gustedt

      Pages 111-122

   10. Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM

       • Kazuo Iwama, Daisuke Kawai, Shuichi Miyazaki, Yasuo Okabe, Jun Umemoto

       Pages 123-134

   11. Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms

       • Peter Sanders, Rudolf Fleischer

       Pages 135-146

   12. Visualizing Algorithms Over the Web with the Publication-Driven Approach

       • Camil Demetrescu, Irene Finocchi, Giuseppe Liotta

       Pages 147-158

   13. Interchanging Tw Segments of an Array in a Hierarchical Memory System

       • Jesper Bojesen, Jyrki Katajainen

       Pages 159-170

   14. Two-Dimensional Arrangements in CGAL and Adaptive Point Location for Parametric Curves

       • Iddo Hanniel, Dan Halperin

       Pages 171-182

   15. Planar Point Location for Large Data Sets: To Seek or Not to Seek

       • Jan Vahrenhold, Klaus H. Hinrichs

       Pages 183-194

   16. Implementation of Approximation Algorithms for Weighted and Unweighted Edge-Disjoint Paths in Bidirected Trees

       • Thomas Erlebach, Klaus Jansen

       Pages 195-206

   17. Dynamic Maintenance Versus Swapping: An Experimental Study on Shortest Paths Trees

       • Guido Proietti

       Pages 207-217

   18. Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study

       • Camil Demetrescu, Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni

       Pages 218-229

This volume contains the papers accepted for the 4th Workshop on Algorithm Engineering (WAE 2000) held in Saarbruc ¨ ken, Germany, during 5–8 September 2000, together with the abstract of the invited lecture given by Karsten Weihe. The Workshop on Algorithm Engineering covers research on all aspects of the subject. The goal is to present recent research results and to identify and explore directions for future research. Previous meetings were held in Venice (1997), Saarbruc ¨ ken (1998), and London (1999). Papers were solicited describing original research in all aspects of algorithm engineering, including: – Development of software repositories and platforms which allow the use of and experimentation with e?cient discrete algorithms. – Novel uses of discrete algorithms in other disciplines and the evaluation of algorithms for realistic environments. – Methodological issues including standards in the context of empirical - search on algorithms and data structures. – Methodological issues regarding the process of converting user requirements into e?cient algorithmic solutions and implementations. The program committee accepted 16 from a total of 30 submissions. The program committee meeting was conducted electronically. The criteria for sel- tion were originality, quality, and relevance to the subject area of the workshop. Considerable e?ort was devoted to the evaluation of the submissions and to p- viding the authors with feedback. Each submission was reviewed by at least four program committee members (assisted by subreferees). A special issue of the ACM Journal of Experimental Algorithmics will be devoted to selected papers from WAE 2000.

• algorithm engineering
• algorithms
• approximation
• combinatorial optimization
• complexity
• computational mathematics
• data structures
• discrete algorithms
• experimental algorithms
• graph algorithms
• searching
• sorting
• string matching
• algorithm analysis and problem complexity

• Universität Trier, Fachbereich IV — Informatik, Trier, Germany

  Stefan Näher

• Fakultät für Mathematik und Informatik, Universität Konstanz, Konstanz, Germany

  Dorothea Wagner

Policies and ethics