Algorithms - ESA 2006

Invited Lectures.- Origami, Linkages, and Polyhedra: Folding with Algorithms.- Reliable and Efficient Geometric Computing.- Some Computational Challenges in Today's Bio-medicine.- Contributed Papers: Design and Analysis Track.- Kinetic Collision Detection for Convex Fat Objects.- Dynamic Connectivity for Axis-Parallel Rectangles.- Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem.- Cooperative TSP.- Fréchet Distance for Curves, Revisited.- Resource Allocation in Bounded Degree Trees.- Dynamic Algorithms for Graph Spanners.- Latency Constrained Aggregation in Sensor Networks.- Competitive Analysis of Flash-Memory Algorithms.- Contention Resolution with Heterogeneous Job Sizes.- Deciding Relaxed Two-Colorability--A Hardness Jump.- Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.- Estimating Entropy over Data Streams.- Necklaces, Convolutions, and X + Y.- Purely Functional Worst Case Constant Time Catenable Sorted Lists.- Taxes for Linear Atomic Congestion Games.- Spanners with Slack.- Compressed Indexes for Approximate String Matching.- Traversing the Machining Graph.- Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games.- Distributed Almost Exact Approximations for Minor-Closed Families.- Spectral Clustering by Recursive Partitioning.- Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data.- Dynamic Programming and Fast Matrix Multiplication.- Near-Entropy Hotlink Assignments.- Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods.- Finding Total Unimodularity in Optimization Problems Solved by Linear Programs.- Preemptive Online Scheduling: Optimal Algorithms for All Speeds.- On the Complexity of theMultiplication Method for Monotone CNF/DNF Dualization.- Lower and Upper Bounds on FIFO Buffer Management in QoS Switches.- Graph Coloring with Rejection.- A Doubling Dimension Threshold ?(loglogn) for Augmented Graph Navigability.- Violator Spaces: Structure and Algorithms.- Region-Restricted Clustering for Geographic Data Mining.- An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths.- Cheating by Men in the Gale-Shapley Stable Matching Algorithm.- Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold.- Enumerating Spanning and Connected Subsets in Graphs and Matroids.- Less Hashing, Same Performance: Building a Better Bloom Filter.- A Unified Approach to Approximating Partial Covering Problems.- Navigating Low-Dimensional and Hierarchical Population Networks.- Popular Matchings in the Capacitated House Allocation Problem.- Inner-Product Based Wavelet Synopses for Range-Sum Queries.- Approximation in Preemptive Stochastic Online Scheduling.- Greedy in Approximation Algorithms.- I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths.- Stochastic Shortest Paths Via Quasi-convex Maximization.- Path Hitting in Acyclic Graphs.- Minimum Transversals in Posi-modular Systems.- An LP-Designed Algorithm for Constraint Satisfaction.- Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing.- Balancing Applied to Maximum Network Flow Problems.- Contributed Papers: Engineering and Applications Track.- Out-of-Order Event Processing in Kinetic Data Structures.- Kinetic Algorithms Via Self-adjusting Computation.- Parallel Machine Scheduling Through Column Generation: Minimax Objective Functions.- Reporting Flock Patterns.- On Exact Algorithms for Treewidth.- An ImprovedConstruction for Counting Bloom Filters.- An MINLP Solution Method for a Water Network Problem.- Skewed Binary Search Trees.- Algorithmic Aspects of Proportional Symbol Maps.- Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?.- Multiline Addressing by Network Flow.- The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression.- The Price of Resiliency: A Case Study on Sorting with Memory Faults.- How Branch Mispredictions Affect Quicksort.- Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces.- Engineering Highway Hierarchies.- Univariate Polynomial Real Root Isolation: Continued Fractions Revisited.- Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method.