Algorithm Engineering and Experimentation: Third International Workshop, ALENEX 2001 Washington, DC, USA, January 5–6, 2001 Revised Papers

Sándor P. Fekete, Henk Meijer, André Rohe, Walter Tietze (auth.), Adam L. Buchsbaum, Jack Snoeyink (eds.)9783540425601, 3540425608

This book constitutes the thoroughly refereed post-proceedings of the Third International Workshop on Algorithm Engineering and Experimentation, ALENEX 2001, held in Washington, DC, USA in January 2001.
The 15 revised full papers presented together with the abstracts of three invited presentations have gone through two rounds of reviewing and revision and were selected from 31 submissions. Among the topics addressed are heuristics for approximation, network optimization, TSP, randomization, sorting, information retrieval, graph computations, tree clustering, scheduling, network algorithms, point set computations, searching, and data mining.

---

Table of contents :
Solving a “Hard” Problem to Approximate an “Easy” One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems….Pages 1-16
CNOP – A Package for Constrained Network Optimization….Pages 17-31
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests….Pages 32-59
Network Tomography through End-to-End Measurements….Pages 60-60
Experimental Results on Statistical Approaches to Page Replacement Policies….Pages 61-77
Estimating Resemblance of MIDI Documents….Pages 78-90
Experiments on Adaptive Set Intersections for Text Retrieval Systems….Pages 91-104
PVD: A Stable Implementation for Computing Voronoi Diagrams of Polygonal Pockets….Pages 105-116
Hierarchical Clustering of Trees: Algorithms and Experiments….Pages 117-131
Travel Planning with Self-Made Maps….Pages 132-144
New Algorithmic Challenges Arising in Measurement-Driven Networking Research….Pages 145-146
A Probabilistic Spell for the Curse of Dimensionality….Pages 147-160
Experimental Evaluation of the Height of a Random Set of Points in a d -Dimensional Cube….Pages 161-171
An Empirical Study of a New Approach to Nearest Neighbor Searching….Pages 172-187
Spectral Analysis for Data Mining….Pages 188-188
Trade Off Between Compression and Search Times in Compact Suffix Array….Pages 189-201
Implementation of a PTAS for Scheduling with Release Dates….Pages 202-215
Biased Skip Lists for Highly Skewed Access Patterns….Pages 216-229