Proc. 8th workshop on algorithm engineering

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. 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 We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R3.