Mark Overmars, Ioannis Karamouzas, Roland Geraerts (auth.), Dan Halperin, Kurt Mehlhorn (eds.)3540877436, 9783540877431
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.
Table of contents :
Front Matter….Pages –
Flexible Path Planning Using Corridor Maps….Pages 1-12
A Bridging Model for Multi-core Computing….Pages 13-28
Robust Kinetic Convex Hulls in 3D….Pages 29-40
On Dominance Reporting in 3D….Pages 41-51
Stabbing Convex Polygons with a Segment or a Polygon….Pages 52-63
An Efficient Algorithm for 2D Euclidean 2-Center with Outliers….Pages 64-75
A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry….Pages 76-87
Cache-Oblivious Red-Blue Line Segment Intersection….Pages 88-99
The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains….Pages 100-111
Space-Time Tradeoffs for Proximity Searching in Doubling Spaces….Pages 112-123
A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem….Pages 124-135
Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs….Pages 136-147
Straight Skeletons of Three-Dimensional Polyhedra….Pages 148-160
Randomized Competitive Analysis for Two-Server Problems….Pages 161-172
Decompositions and Boundary Coverings of Non-convex Fat Polyhedra….Pages 173-184
Approximating Multi-criteria Max-TSP….Pages 185-197
An Integer Programming Algorithm for Routing Optimization in IP Networks….Pages 198-209
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling….Pages 210-221
Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree….Pages 222-233
Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors….Pages 234-245
A Practical Quicksort Algorithm for Graphics Processors….Pages 246-258
Bloomier Filters: A Second Look….Pages 259-270
Coupled Path Planning, Region Optimization, and Applications in Intensity-Modulated Radiation Therapy….Pages 271-283
A New Approach to Exact Crossing Minimization….Pages 284-296
A Characterization of 2-Player Mechanisms for Scheduling….Pages 297-307
A Local-Search 2-Approximation for 2-Correlation-Clustering….Pages 308-319
The Alcuin Number of a Graph….Pages 320-331
Time-Dependent SHARC-Routing….Pages 332-343
Detecting Regular Visit Patterns….Pages 344-355
Improved Approximation Algorithms for Relay Placement….Pages 356-367
Selfish Bin Packing….Pages 368-380
Improved Randomized Results for That Interval Selection Problem….Pages 381-392
Succinct Representations of Arbitrary Graphs….Pages 393-404
Edge Coloring and Decompositions of Weighted Graphs….Pages 405-416
The Complexity of Sorting with Networks of Stacks and Queues….Pages 417-429
Faster Steiner Tree Computation in Polynomial-Space….Pages 430-441
Fitting a Step Function to a Point Set….Pages 442-453
Faster Swap Edge Computation in Minimum Diameter Spanning Trees….Pages 454-465
The Partial Augment–Relabel Algorithm for the Maximum Flow Problem….Pages 466-477
An Optimal Dynamic Spanner for Doubling Metric Spaces….Pages 478-489
RFQ: Redemptive Fair Queuing….Pages 490-502
Range Medians….Pages 503-514
Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves….Pages 515-527
Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison….Pages 528-539
On the Complexity of Optimal Hotlink Assignment….Pages 540-552
Oblivious Randomized Direct Search for Real-Parameter Optimization….Pages 553-564
Path Minima in Incremental Unrooted Trees….Pages 565-576
Improved Competitive Performance Bounds for CIOQ Switches….Pages 577-588
Two-Stage Robust Network Design with Exponential Scenarios….Pages 589-600
An Optimal Incremental Algorithm for Minimizing Lateness with Rejection….Pages 601-610
More Robust Hashing: Cuckoo Hashing with a Stash….Pages 611-622
Better and Simpler Approximation Algorithms for the Stable Marriage Problem….Pages 623-634
Edit Distances and Factorisations of Even Permutations….Pages 635-646
Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count….Pages 647-659
Facility Location in Dynamic Geometric Data Streams….Pages 660-671
The Effects of Local Randomness in the Adversarial Queueing Model….Pages 672-683
Parallel Imaging Problem….Pages 684-695
An Online Algorithm for Finding the Longest Previous Factors….Pages 696-707
Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions….Pages 708-719
Improved BDD Algorithms for the Simulation of Quantum Circuits….Pages 720-731
Mobile Route Planning….Pages 732-743
How Reliable Are Practical Point-in-Polygon Strategies?….Pages 744-755
Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach….Pages 756-767
Approximability of Average Completion Time Scheduling on Unrelated Machines….Pages 768-779
Relative Convex Hulls in Semi-dynamic Subdivisions….Pages 780-792
An Experimental Analysis of Robinson-Foulds Distance Matrix Algorithms….Pages 793-804
On the Size of the 3D Visibility Skeleton: Experimental Results….Pages 805-816
An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions….Pages 817-829
Deterministic Sampling Algorithms for Network Design….Pages 830-841
Back Matter….Pages –
Reviews
There are no reviews yet.