Algorithms - ESA 2008

This book constitutes the refereed proceedings of the 16th Annual European Symposium on Algorithms, ESA 2008, held in Karlsruhe, Germany, in September 2008 in the context of the combined conference ALGO 2008.

The 67 revised full papers presented together with 2 invited lectures were carefully reviewed and selected: 51 papers out of 147 submissions for the design and analysis track and 16 out of 53 submissions in the engineering and applications track. The papers address all current subjects in algorithmics reaching from design and analysis issues of algorithms over to real-world applications and engineering of algorithms in various fields. Special focus is given to mathematical programming and operations research, including combinatorial optimization, integer programming, polyhedral combinatorics and network optimization.

Inhalt

Invited Lectures.- Flexible Path Planning Using Corridor Maps.- A Bridging Model for Multi-core Computing.- Contributed Papers.- Robust Kinetic Convex Hulls in 3D.- On Dominance Reporting in 3D.- Stabbing Convex Polygons with a Segment or a Polygon.- An Efficient Algorithm for 2D Euclidean 2-Center with Outliers.- A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry.- Cache-Oblivious Red-Blue Line Segment Intersection.- The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains.- Space-Time Tradeoffs for Proximity Searching in Doubling Spaces.- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem.- Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs.- Straight Skeletons of Three-Dimensional Polyhedra.- Randomized Competitive Analysis for Two-Server Problems.- Decompositions and Boundary Coverings of Non-convex Fat Polyhedra.- Approximating Multi-criteria Max-TSP.- An Integer Programming Algorithm for Routing Optimization in IP Networks.- A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling.- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree.- Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors.- A Practical Quicksort Algorithm for Graphics Processors.- Bloomier Filters: A Second Look.- Coupled Path Planning, Region Optimization, and Applications in Intensity-Modulated Radiation Therapy.- A New Approach to Exact Crossing Minimization.- A Characterization of 2-Player Mechanisms for Scheduling.- A Local-Search 2-Approximation for 2-Correlation-Clustering.- The Alcuin Number of a Graph.- Time-Dependent SHARC-Routing.- Detecting Regular Visit Patterns.- Improved Approximation Algorithms for Relay Placement.- Selfish Bin Packing.- Improved Randomized Results for That Interval Selection Problem.- Succinct Representations of Arbitrary Graphs.- Edge Coloring and Decompositions of Weighted Graphs.- The Complexity of Sorting with Networks of Stacks and Queues.- Faster Steiner Tree Computation in Polynomial-Space.- Fitting a Step Function to a Point Set.- Faster Swap Edge Computation in Minimum Diameter Spanning Trees.- The Partial Augment-Relabel Algorithm for the Maximum Flow Problem.- An Optimal Dynamic Spanner for Doubling Metric Spaces.- RFQ: Redemptive Fair Queuing.- Range Medians.- Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves.- Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison.- On the Complexity of Optimal Hotlink Assignment.- Oblivious Randomized Direct Search for Real-Parameter Optimization.- Path Minima in Incremental Unrooted Trees.- Improved Competitive Performance Bounds for CIOQ Switches.- Two-Stage Robust Network Design with Exponential Scenarios.- An Optimal Incremental Algorithm for Minimizing Lateness with Rejection.- More Robust Hashing: Cuckoo Hashing with a Stash.- Better and Simpler Approximation Algorithms for the Stable Marriage Problem.- Edit Distances and Factorisations of Even Permutations.- Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count.- Facility Location in Dynamic Geometric Data Streams.- The Effects of Local Randomness in the Adversarial Queueing Model.- Parallel Imaging Problem.- An Online Algorithm for Finding the Longest Previous Factors.- Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions.- Improved BDD Algorithms for the Simulation of Quantum Circuits.- Mobile Route Planning.- How Reliable Are Practical Point-in-Polygon Strategies?.- Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times - A Polymatroid Optimization Approach.- Approximability of Average Completion Time Scheduling on Unrelated Machines.- Relative Convex Hulls in Semi-dynamic Subdivisions.- An Experimental Analysis of Robinson-Foulds Distance Matrix Algorithms.- On the Size of the 3D Visibility Skeleton: Experimental Results.- An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions.- Deterministic Sampling Algorithms for Network Design.