Experimental Algorithms: 14th International Symposium, SEA 2015, Paris, France, June 29 – July 1, 2015, Proceedings (Lecture Notes in Computer Science, 9125)

This book constitutes the refereed proceedings of the 14th International Symposium on Experimental Algorithms, SEA 2015, held in Paris, France, in June/July 2015. The 30 revised full papers presented were carefully reviewed and selected from 76 submissions. The main theme of the symposium is the role of experimentation and of algorithm engineering techniques in the design and evaluation of algorithms and data structures. The papers are grouped in topical sections on data structures, graph problems, combinatorial optimization, scheduling and allocation, and transportation networks. Front Matter....Pages I-XI Front Matter....Pages 1-1 Parallel Construction of Succinct Trees....Pages 3-14 Tree Compression with Top Trees Revisited....Pages 15-27 A Bulk-Parallel Priority Queue in External Memory with STXXL....Pages 28-40 Front Matter....Pages 41-41 Greedily Improving Our Own Centrality in A Network....Pages 43-55 An Exact Algorithm for Diameters of Large Real Directed Graphs....Pages 56-67 Graph Partitioning for Independent Sets....Pages 68-81 Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments....Pages 82-93 Front Matter....Pages 95-95 On the Generation of Cutting Planes which Maximize the Bound Improvement....Pages 97-109 Separation of Generic Cutting Planes in Branch-and-Price Using a Basis....Pages 110-121 On a Nonconvex MINLP Formulation of the Euclidean Steiner Tree Problem in n-Space....Pages 122-133 Front Matter....Pages 135-135 Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors....Pages 137-150 Station Assignment with Reallocation....Pages 151-164 Online Knapsack of Unknown Capacity:....Pages 165-177 Front Matter....Pages 179-179 Reoptimization Techniques for MIP Solvers....Pages 181-192 Submodular Minimization in the Context of Modern LP and MILP Methods and Solvers....Pages 193-204 Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver....Pages 205-218 Efficient and Practical Tree Preconditioning for Solving Laplacian Systems....Pages 219-231 Front Matter....Pages 233-233 Efficient Generation of Stable Planar Cages for Chemistry....Pages 235-246 Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment....Pages 247-258 Solving k-means on High-Dimensional Big Data....Pages 259-270 Front Matter....Pages 271-271 Public Transit Labeling....Pages 273-285 On Balanced Separators in Road Networks....Pages 286-297 SALT. A Unified Framework for All Shortest-Path Query Variants on Road Networks....Pages 298-311 Front Matter....Pages 313-313 Huffman Codes versus Augmented Non-Prefix-Free Codes....Pages 315-326 Experimental Analysis of an Online Dictionary Matching Algorithm for Regular Expressions with Gaps....Pages 327-338 An Empirical Study of Finding Approximate Equilibria in Bimatrix Games....Pages 339-351 The Effect of Almost-Empty Faces on Planar Kandinsky Drawings....Pages 352-364 Front Matter....Pages 365-365 An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem....Pages 367-378 On the Quadratic Shortest Path Problem....Pages 379-390 A Solution Merging Heuristic for the Steiner Problem in Graphs Using Tree Decompositions....Pages 391-402 Back Matter....Pages 403-404