Proc. 8th workshop on algorithm engineering

Rajeev Raman, Robert Sedgewick, Matthias F. Stallmann0898716101, 9780898716108

Workshops held in Miami, Florida, January 21, 2006.
The annual Workshop on Algorithm Engineering and Experiments (ALENEX) provides a forum for the presentation of original research in all aspects of algorithm engineering, including the implementation and experimental evaluation of algorithms and data structures. The workshop was sponsored by SIAM, the Society for Industrial and Applied Mathematics, and SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. The aim of ANALCO is to provide a forum for the presentation of original research in the analysis of algorithms and associated combinatorial structures.

---

Table of contents :
PROCEEDINGS OF THE EIGHTH WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS AND THE THIRD WORKSHOP ON ANALYTIC ALGORITHMICS AND COMBINATORICS……Page 1
CONTENTS……Page 6
ALENEX WORKSHOP PREFACE……Page 8
ANALCO WORKSHOP PREFACE……Page 10
Workshop on Algorithm Engineering and Experiments……Page 12
Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications*……Page 14
An Experimental Study of Point Location in General Planar Arrangements*……Page 27
Summarizing Spatial Data Streams Using ClusterHulls……Page 37
Distance-Sensitive Bloom Filters……Page 52
An Experimental Study of Old and New Depth Measures*……Page 62
Keep Your Friends Close and Your Enemies Closer: The Art of Proximity Searching……Page 76
Implementation and Experiments with an Algorithm forParallel Scheduling of Complex Dags under Uncertainty* (Extended Abstract)……Page 77
Using Markov Chains To Design Algorithms For Bounded-Space On-Line Bin Cover……Page 86
Data Reduction, Exact, and Heuristic Algorithms for Clique Cover……Page 97
Fast Reconfiguration of Data Placement in Parallel Disks……Page 106
Force-Directed Approaches to Sensor Localization*……Page 119
Compact Routing on Power Law Graphs with Additive Stretch*……Page 130
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms……Page 140
Distributed Routing in Small-World Networks……Page 155
Engineering Multi-Level Overlay Graphs for Shortest-Path Queries*……Page 167
Optimal Incremental Sorting *……Page 182
Workshop on Analytic Algorithmics and Combinatorics……Page 194
Deterministic Random Walks*……Page 196
Binary Trees, Left and Right Paths, WKB Expansions, and Painleve Transcendents*……Page 209
On the Variance of Quickselect*……Page 216
Semirandom Models as Benchmarks for Coloring Algorithms……Page 222
New Results and Open Problems for Deletion Channels……Page 233
Partial Fillup and Search Time in LC Tries*……Page 234
Distinct Values Estimators for Power Law Distributions……Page 241
A Random-Surfer Web-Graph Model……Page 249
Asymptotic Optimality of the Static Frequency Caching in the Presence of Correlated Requests*……Page 258
Exploring the Average Values of Boolean Functions via Asymptotics and Experimentation……Page 264
Permanents of Circulants: a Transfer Matrix Approach* (Extended Abstract)……Page 274
Random partitions with parts in the range of a polynomial*……Page 284
AUTHOR INDEX……Page 292