Proceedings of the 6th Workshop on Algorithm Engineering and 1st workshop on Combinatorics

Lars Arge9780898715644, 0898715644

The aim of the annual ALENEX workshop is to provide a forum for the presentation of original research in the implementation and experimental evaluation of algorithms and data structures. This research presents significant studies in experimental analysis or in the implementation, testing, and evaluation of algorithms for realistic environments and scenarios. The paper presentations address specific applied areas that present unique challenges in their underlying algorithmic problems as well as methodological issues and standards in the context of empirical research on algorithms and data structures. The ANALCO workshop presents a collection of original research in the analysis of algorithms and associated combinatorial structures. The papers study properties of fundamental combinatorial structures that arise in practical computational applications (such as permutations, trees, strings, tries, and graphs) and address the precise analysis of algorithms for processing such structures, including average-case analysis; analysis of moments, extrema, and distributions; and probabilistic analysis of randomized algorithms. This proceedings collects extended versions of the 14 papers that were selected for presentation from the ALENEX workshop and 10 papers selected for presentation from the ANALCO workshop.

---

Table of contents :
PROCEEDINGS OF THE SIXTH WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS AND THE FIRST WORKSHOP ON ANALYTIC ALGORITHMICS AND COMBINATORICS……Page 1
CONTENTS……Page 8
ALENEX WORKSHOP PREFACE……Page 10
ANALCO WORKSHOP PREFACE……Page 12
Workshop on Algorithm Engineering and Experiments……Page 14
Engineering Geometric Algorithms: Persistent Problems and Some Solutions……Page 16
Engineering a Cache-Oblivious Sorting Algorithm*……Page 17
The Robustness of the Sum-of-Squares Algorithm for Bin Packing……Page 31
Practical Aspects of Compressed Suffix Arrays and FM-index in Searching DNA Sequences……Page 44
Faster placement of hydrogens in protein structures by dynamic programming……Page 52
An Experimental Analysis of a Compact Graph Representation……Page 62
Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments*……Page 75
Safe Separators for Treewidth*……Page 83
Efficient Implementation of a Hotlink Assignment Algorithm for Web Sites……Page 92
Experimental Comparison of Shortest Path Approaches for Timetable Information*……Page 101
Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks……Page 113
Lazy Algorithms for Dynamic Closest Pair with Arbitrary Distance Measures……Page 125
Approximating the Visible Region of a Point on a Terrain1……Page 133
A computational framework for handling motion……Page 142
Engineering a Sorted List Data Structure for 32 Bit Keys*……Page 155
Workshop on Analytic Algorithmics and Combinatorics……Page 164
Theory and Practice of Probabilistic Counting Algorithms……Page 165
Analysis of a Randomized Selection Algorithm Motivated by the LZ’77 Scheme……Page 166
The Complexity of Jensen’s Algorithm for Counting Polyominoes……Page 174
Distributional Analyses of Euclidean Algorithms……Page 183
A Simple Primality Test and the rth Smallest Prime Factor……Page 198
Gap-free samples of geometric random variables – Extended Abstract……Page 207
Computation of a Class of Continued Fraction Constants……Page 212
Compositions and Patricia tries: no fluctuations in the variance!……Page 224
Quadratic Convergence for Scaling of Matrices……Page 229
Partial Quicksort……Page 237
AUTHOR INDEX……Page 242