Algorithms – ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006. Proceedings

Erik D. Demaine (auth.), Yossi Azar, Thomas Erlebach (eds.)3540388753, 9783540388753

This book constitutes the refereed proceedings of the 14th Annual European Symposium on Algorithms, ESA 2006, held in Zurich, Switzerland, in September 2006, in the context of the combined conference ALGO 2006.

The 70 revised full papers presented together with abstracts of 3 invited lectures were carefully reviewed and selected from 287 submissions. 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.

---

Table of contents :
Front Matter….Pages –
Origami, Linkages, and Polyhedra: Folding with Algorithms….Pages 1-1
Reliable and Efficient Geometric Computing….Pages 2-2
Some Computational Challenges in Today’s Bio-medicine….Pages 3-3
Kinetic Collision Detection for Convex Fat Objects….Pages 4-15
Dynamic Connectivity for Axis-Parallel Rectangles….Pages 16-27
Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem….Pages 28-39
Cooperative TSP….Pages 40-51
Fréchet Distance for Curves, Revisited….Pages 52-63
Resource Allocation in Bounded Degree Trees….Pages 64-75
Dynamic Algorithms for Graph Spanners….Pages 76-87
Latency Constrained Aggregation in Sensor Networks….Pages 88-99
Competitive Analysis of Flash-Memory Algorithms….Pages 100-111
Contention Resolution with Heterogeneous Job Sizes….Pages 112-123
Deciding Relaxed Two-Colorability—A Hardness Jump….Pages 124-135
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables….Pages 136-147
Estimating Entropy over Data Streams….Pages 148-159
Necklaces, Convolutions, and X + Y ….Pages 160-171
Purely Functional Worst Case Constant Time Catenable Sorted Lists….Pages 172-183
Taxes for Linear Atomic Congestion Games….Pages 184-195
Spanners with Slack….Pages 196-207
Compressed Indexes for Approximate String Matching….Pages 208-219
Traversing the Machining Graph….Pages 220-231
Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games….Pages 232-243
Distributed Almost Exact Approximations for Minor-Closed Families….Pages 244-255
Spectral Clustering by Recursive Partitioning….Pages 256-267
Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data….Pages 268-279
Dynamic Programming and Fast Matrix Multiplication….Pages 280-291
Near-Entropy Hotlink Assignments….Pages 292-303
Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods….Pages 304-314
Finding Total Unimodularity in Optimization Problems Solved by Linear Programs….Pages 315-326
Preemptive Online Scheduling: Optimal Algorithms for All Speeds….Pages 327-339
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization….Pages 340-351
Lower and Upper Bounds on FIFO Buffer Management in QoS Switches….Pages 352-363
Graph Coloring with Rejection….Pages 364-375
A Doubling Dimension Threshold Θ(loglog n ) for Augmented Graph Navigability….Pages 376-386
Violator Spaces: Structure and Algorithms….Pages 387-398
Region-Restricted Clustering for Geographic Data Mining….Pages 399-410
An O ( n 3 (loglog n /log n ) 5/4 ) Time Algorithm for All Pairs Shortest Paths….Pages 411-417
Cheating by Men in the Gale-Shapley Stable Matching Algorithm….Pages 418-431
Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold….Pages 432-443
Enumerating Spanning and Connected Subsets in Graphs and Matroids….Pages 444-455
Less Hashing, Same Performance: Building a Better Bloom Filter….Pages 456-467
A Unified Approach to Approximating Partial Covering Problems….Pages 468-479
Navigating Low-Dimensional and Hierarchical Population Networks….Pages 480-491
Popular Matchings in the Capacitated House Allocation Problem….Pages 492-503
Inner-Product Based Wavelet Synopses for Range-Sum Queries….Pages 504-515
Approximation in Preemptive Stochastic Online Scheduling….Pages 516-527
Greedy in Approximation Algorithms….Pages 528-539
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths….Pages 540-551
Stochastic Shortest Paths Via Quasi-convex Maximization….Pages 552-563
Path Hitting in Acyclic Graphs….Pages 564-575
Minimum Transversals in Posi-modular Systems….Pages 576-587
An LP-Designed Algorithm for Constraint Satisfaction….Pages 588-599
Approximate k -Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing….Pages 600-611
Balancing Applied to Maximum Network Flow Problems….Pages 612-623
Out-of-Order Event Processing in Kinetic Data Structures….Pages 624-635
Kinetic Algorithms Via Self-adjusting Computation….Pages 636-647
Parallel Machine Scheduling Through Column Generation: Minimax Objective Functions….Pages 648-659
Reporting Flock Patterns….Pages 660-671
On Exact Algorithms for Treewidth….Pages 672-683
An Improved Construction for Counting Bloom Filters….Pages 684-695
An MINLP Solution Method for a Water Network Problem….Pages 696-707
Skewed Binary Search Trees….Pages 708-719
Algorithmic Aspects of Proportional Symbol Maps….Pages 720-731
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?….Pages 732-743
Multiline Addressing by Network Flow….Pages 744-755
The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression….Pages 756-767
The Price of Resiliency: A Case Study on Sorting with Memory Faults….Pages 768-779
How Branch Mispredictions Affect Quicksort….Pages 780-791
Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces….Pages 792-803
Engineering Highway Hierarchies….Pages 804-816
Univariate Polynomial Real Root Isolation: Continued Fractions Revisited….Pages 817-828
Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method….Pages 829-840
Back Matter….Pages –