Algorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014 : proceedings

This book constitutes the refereed proceedings of the 22st Annual European Symposium on Algorithms, ESA 2014, held in Wrocław, Poland, in September 2014, as part of ALGO 2014. The 69 revised full papers presented were carefully reviewed and selected from 269 initial submissions: 57 out of 221 in Track A, Design and Analysis, and 12 out of 48 in Track B, Engineering and Applications. The papers present original research in the areas of design and mathematical analysis of algorithms; engineering, experimental analysis, and real-world applications of algorithms and data structures. Front Matter....Pages - Losing Weight by Gaining Edges....Pages 1-12 Optimal Coordination Mechanisms for Multi-job Scheduling Games....Pages 13-24 Theory and Practice of Chunked Sequences....Pages 25-36 Convex Hulls under Uncertainty....Pages 37-48 The Space-Stretch-Time Tradeoff in Distance Oracles....Pages 49-60 Distribution-Sensitive Construction of the Greedy Spanner....Pages 61-73 Recognizing Shrinkable Complexes Is NP-Complete....Pages 74-86 Improved Approximation Algorithms for Box Contact Representations....Pages 87-99 Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms....Pages 100-111 The Batched Predecessor Problem in External Memory....Pages 112-124 Polynomial Decompositions in Polynomial Time....Pages 125-136 Fault-Tolerant Approximate Shortest-Path Trees....Pages 137-148 Fast Witness Extraction Using a Decision Oracle....Pages 149-160 Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model....Pages 161-172 A Subexponential Parameterized Algorithm for Proper Interval Completion....Pages 173-184 Computing Persistent Homology with Various Coefficient Fields in a Single Pass....Pages 185-196 De-anonymization of Heterogeneous Random Graphs in Quasilinear Time....Pages 197-208 Competitive Algorithms for Restricted Caching and Matroid Caching....Pages 209-221 Improved Algorithms for Resource Allocation under Varying Capacity....Pages 222-234 Nearly Tight Approximability Results for Minimum Biclique Cover and Partition....Pages 235-246 Succinct Indices for Path Minimum, with Applications to Path Reporting....Pages 247-259 Online Bipartite Matching with Decomposable Weights....Pages 260-271 A Faster Algorithm for Computing Straight Skeletons....Pages 272-283 Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem....Pages 284-295 Cache-Oblivious Persistence....Pages 296-308 Lightweight Approximate Selection....Pages 309-320 Robust Distance Queries on Massive Networks....Pages 321-333 A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-Depth....Pages 334-345 Large Independent Sets in Triangle-Free Planar Graphs....Pages 346-357 GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem....Pages 358-370 Switching Colouring of G ( n , d / n ) for Sampling up to Gibbs Uniqueness Threshold....Pages 371-381 From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?....Pages 382-393 Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs....Pages 394-405 Bicriteria Data Compression: Efficient and Usable....Pages 406-417 Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs....Pages 418-429 LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs....Pages 430-442 Representative Sets of Product Families....Pages 443-454 Weighted Ancestors in Suffix Trees....Pages 455-466 Improved Practical Matrix Sketching with Guarantees....Pages 467-479 Computing Regions Decomposable into m Stars....Pages 480-491 The Parameterized Complexity of Graph Cyclability....Pages 492-504 Dimension Reduction via Colour Refinement....Pages 505-516 How Experts Can Solve LPs Online....Pages 517-529 Parameterized Complexity of the k -Arc Chinese Postman Problem....Pages 530-541 Approximating the Maximum Overlap of Polygons under Translation....Pages 542-553 Ordering without Forbidden Patterns....Pages 554-565 Halving Balls in Deterministic Linear Time....Pages 566-578 Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes....Pages 579-591 Optimal Parallel Quantum Query Algorithms....Pages 592-604 Sublinear Space Algorithms for the Longest Common Substring Problem....Pages 605-617 Nested Set Union....Pages 618-629 Improved Explicit Data Structures in the Bitprobe Model....Pages 630-641 Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees....Pages 642-653 FPTAS for Counting Weighted Edge Covers....Pages 654-665 Solving Multicut Faster Than 2 n ....Pages 666-676 Tight Bounds for Active Self-assembly Using an Insertion Primitive....Pages 677-688 Trace Reconstruction Revisited....Pages 689-700 PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies....Pages 701-712 Polynomial-Time Approximation Schemes for Circle Packing Problems....Pages 713-724 Document Retrieval on Repetitive Collections....Pages 725-736 An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs....Pages 737-749 The Input/Output Complexity of Sparse Matrix Multiplication....Pages 750-761 Faster FPTASes for Counting and Random Generation of Knapsack Solutions....Pages 762-773 Improved Guarantees for Tree Cut Sparsifiers....Pages 774-785 Representative Families: A Unified Tradeoff-Based Approach....Pages 786-797 A Branch and Price Procedure for the Container Premarshalling Problem....Pages 798-809 Space-Efficient Randomized Algorithms for K-SUM....Pages 810-829 Equivalence between Priority Queues and Sorting in External Memory....Pages 830-841 Amortized Bounds for Dynamic Orthogonal Range Reporting....Pages 842-856 Back Matter....Pages - This book constitutes the refereed proceedings of the 22st Annual European Symposium on Algorithms, ESA 2014, held in Wroc¿ aw, Poland, in September 2014, as part of ALGO 2014. The 69 revised full papers presented were carefully reviewed and selected from 269 initial submissions: 57 out of 221 in Track A, Design and Analysis, and 12 out of 48 in Track B, Engineering and Applications. The papers present original research in the areas of design and mathematical analysis of algorithms; engineering, experimental analysis, and real-world applications of algorithms and data structures