Algorithm Engineering and Experimentation

ALENEX’01

1. Solving a “Hard” Problem to Approximate an “Easy” One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems

   • Sándor P. Fekete, Henk Meijer, André Rohe, Walter Tietze

   Pages 1-16

2. CNOP - A Package for Constrained Network Optimization

   • K. Mehlhorn, M. Ziegelmann

   Pages 17-31

3. The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests

   • Jill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang

   Pages 32-59

4. Network Tomography through End-to-End Measurements

   • Don Towsley

   Pages 60-60

5. Experimental Results on Statistical Approaches to Page Replacement Policies

   • Vitus Leung, Sandy Irani

   Pages 61-77

6. Estimating Resemblance of MIDI Documents

   • Michael Mitzenmacher, Sean Owen

   Pages 78-90

7. Experiments on Adaptive Set Intersections for Text Retrieval Systems

   • Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro

   Pages 91-104

8. PVD: A Stable Implementation for Computing Voronoi Diagrams of Polygonal Pockets

   • Saurabh Sethia, Martin Held, Joseph S. B. Mitchell

   Pages 105-116

9. Hierarchical Clustering of Trees: Algorithms and Experiments

   • Irene Finocchi, Rossella Petreschi

   Pages 117-131

10. Travel Planning with Self-Made Maps

    • Ulrik Brandes, Frank Schulz, Dorothea Wagner, Thomas Willhalm

    Pages 132-144

11. New Algorithmic Challenges Arising in Measurement-Driven Networking Research

    • Walter Willinger

    Pages 145-146

12. A Probabilistic Spell for the Curse of Dimensionality

    • Edgar Chávez, Gonzalo Navarro

    Pages 147-160

13. Experimental Evaluation of the Height of a Random Set of Points in a d-Dimensional Cube

    • Eric Breimer, Mark Goldberg, Brian Kolstad, Malik Magdon-Ismail

    Pages 161-171

14. An Empirical Study of a New Approach to Nearest Neighbor Searching

    • Songrit Maneewongvatana, David M. Mount

    Pages 172-187

15. Spectral Analysis for Data Mining

    • Anna R. Karlin

    Pages 188-188

16. Trade Off Between Compression and Search Times in Compact Suffix Array

    • Veli Mäkinen

    Pages 189-201

17. Implementation of a PTAS for Scheduling with Release Dates

    • Clint Hepner, Cliff Stein

    Pages 202-215

18. Biased Skip Lists for Highly Skewed Access Patterns

    • Funda Ergun, S. Cenk Şahinalp, Jonathan Sharp, Rakesh K. Sinha

    Pages 216-229