Experimental Algorithms
11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings
Published on 28. May 2012
XIII, 406 pages
978-3-642-30850-5 (ISBN)
Description
This book constitutes the refereed proceedings of the 11th International Symposium on Experimental Algorithms, SEA 2012, held Bordeaux, France, in June 2012. The 31 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 64 submissions and present current research in the area of design, analysis, and experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications.
More details
Other editions
Additional editions
Ralf Klasing
Experimental Algorithms
11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings
Book
05/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Papers
- Automatic Decomposition and Branch-and-Price-A Status Report
- Modeling with Integer Programs
- Dantzig-Wolfe Reformulation
- In Need for an Automatic Decomposition
- Recognizing Matrix Structures for Decomposition
- Towards a Standalone Solver
- Discussion
- References
- Continuous Local Strategies for Robotic Formation Problems
- Introduction
- The Robot Chain Problem
- The Gathering Problem
- Discussion of Models and Strategies
- References
- Engineering Graph Partitioning Algorithms
- Introduction
- Karlsruhe Parallel Partitioner [5]
- The n-Level Approach [6]
- Karlsruhe Fast Flow Partitioner [7]
- KaFFPa Evolutionary [8]
- 10th DIMACS Implementation Challenge
- Conclusions and Future Work
- References
- Contributed Papers
- Space Efficient Modifications to Structator- A Fast Index-Based Search Tool for RNA Sequence-Structure Patterns
- Introduction
- Structator-A Fast Index-Based Search Tool for RNA Sequence-Structure Patterns
- Formal Definitions
- Modifications to Structator
- Computation of Affix Links via Binary Search
- Computation of Affix Links via Improved Binary Search
- Experiments
- Four Different Modes
- 1st Experiment-Memory vs. Runtime
- 2nd Experiment-Mode IBS vs. Mode BS
- Conclusion
- References
- Implementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphs
- Introduction
- General Description
- Results and Observations
- General Synthesis
- References
- How to Attack the NP-Complete Dag Realization Problem in Practice
- The Dag Realization Problem
- Lessons from Experiments with the Lexmax Strategy
- Randomized Algorithms
- Four Versions of Randomized Algorithms
- Experimental Comparison of Randomized Algorithms
- Conclusion
- References
- New Results about Multi-band Uncertainty in Robust Optimization
- Introduction
- Model and Notation
- A Compact Robust LP Counterpart
- Separation of Robustness Cuts
- Computational Study
- Conclusions and Future Work
- References
- Compact Relaxations for Polynomial Programming Problems
- Introduction
- rRLT for Polynomial Programming
- Compact Convex Relaxation
- Convexity Gap
- Choosing a Good Basis for the Companion System
- Dealing with Sparsity
- Bipartite Matching Based Algorithm for (10)
- Computational Results
- References
- Relaxations of Multilinear Convex Envelopes: Dual Is Better Than Primal
- Introduction
- Contributions
- Applications
- Exact Linearizations
- Products of Continuous Variables
- Convex Envelopes of Multilinear Terms
- McCormick's Inequalities
- Meyer-Floudas Inequalities
- Quadrilinear Terms
- Critique
- Dual Envelopes
- Relaxations
- Computational Results
- References
- On Computing the Diameter of Real-World Directed (Weighted) Graphs
- Introduction
- The DiFUB Algorithm
- Experiments
- Obtaining a Tight Lower Bound via 2-dSWEEP
- Obtaining the Diameter via DiFUB
- The DiFUB Algorithm for Weighted Graphs
- Dataset and Experiments
- Conclusion and Open Questions
- References
- Reoptimizing the Strengthened Metric TSP on Multiple Edge Weight Modifications
- Introduction
- Reoptimizing the Strengthened Metric TSP
- Experimental Results
- References
- Engineering a New Loop-Free Shortest Paths Routing Algorithm
- Introduction
- Preliminaries
- The New Algorithm
- Experimental Analysis
- References
- Fully Dynamic Maintenance of Arc-Flags in Road Networks
- Introduction
- Preliminaries
- Incremental Update of Arc-Flags
- Experimental Study
- References
- A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs
- Introduction
- Our Results
- Overview of the Paper
- Greedy Matching Heuristics
- Experiments
- Results
- Summary and Future Work
- References
- Branch Mispredictions Don't Affect Mergesort
- Introduction
- Tuned Mergesort
- Tuned In-Situ Mergesort
- Comparison to Quicksort
- Advice for Practitioners
- Afterword
- References
- A Multiple Sliding Windows Approach to Speed Up String Matching Algorithms
- Introduction
- Notations and Terminology
- A General Multiple Sliding Windows Approach
- Multiple Windows Variants of Bit-Parallel Algorithms
- Multiple Windows Variants of Comparison Based Algorithms
- Experimental Results
- Conclusions
- References
- Algorithms for Subnetwork Mining in Heterogeneous Networks
- Introduction
- The Problem
- The Complexity of SkewGraM
- Two Algorithms for SkewGraM
- Experimental Results
- Performances of AlgoH
- Applying AlgoH on Biological Networks
- Conclusion
- References
- Computing Strong Articulation Points and Strong Bridges in Large Scale Graphs
- Introduction
- Graph Terminology
- Experimental Setup
- Algorithms for Strong Articulation Points and Strong Bridges
- Experimental Results
- References
- Adaptive Distributed b-Matching in Overlays with Preferences
- Introduction
- Related Work
- Problem Definition and System Model
- Improved Approximation Ratio
- Adaptive Matching Algorithm
- Analysis
- Experimental Study
- Network Types
- Convergence and Reconvergence
- Satisfaction
- Conclusions
- References
- Dynamizing Succinct Tree Representations
- Introduction
- Preliminaries
- Traversals on Static Trees
- Engineering a Dynamic Succinct Implementation
- Experimental Evaluation
- Conclusions
- References
- A Label Correcting Algorithm for the Shortest Path Problem on a Multi-modal Route Network
- Introduction
- Preliminaries
- Solving the RegLCSP
- SDALT
- Label Correcting State Dependent uniALT: lcSDALT
- Query
- Constrained Landmark Distances
- Experimental Results
- Discussion of Experimental Results and Conclusive Remarks
- References
- Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data
- Introduction
- Preliminaries
- ZDD Approach
- Introduction to ZDDs
- ZDD-Based Enumeration Algorithm
- Example with Huge Compression
- Hardness of Counting
- Experiments
- Conclusion
- References
- Candidate Sets for Alternative Routes in Road Networks
- Introduction and Related Work
- The Baseline Algorithm
- Engineering the Baseline Algorithm
- Single-Level via Node Candidates
- Multi-level via Node Candidates
- Further Engineering
- Experiments
- Methodology
- Engineered Baseline Algorithm
- Preprocessed Candidate Sets
- Conclusion and Future Work
- References
- Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation
- Introduction
- The NLDKSS Optimality Criteria
- Finding an Optimal Solution
- NLDKSS in Practice
- Data Analysis Software and Empirical Results
- Future Work
- References
- An Evaluation of Community Detection Algorithms on Large-Scale Email Traffic
- Introduction
- Quality of Community Detection Algorithms
- Studied Community Detection Algorithms
- Related Work
- Experimental Evaluation
- Dataset
- Comparison of the Algorithms
- Conclusions
- References
- Fast, Small, Simple Rank/Select on Bitmaps
- Introduction
- Related Work
- A Structure for Compressed Bitmaps
- A Structure for Plain Bitmaps: Combined Sampling
- Experimental Results
- Compressed Representations
- Combined Sampling
- Applications
- Conclusions
- References
- Space-Efficient Top-k Document Retrieval
- Introduction
- Related Work
- Implementing Hon et al.'s Succinct Structure
- Sparsified Generalized Suffix Tree (SGST)
- Succinct SGST
- A New Top-k Algorithm
- Restricted Depth-First Search (DFS)
- Restricted Greedy
- Heaps for the k Most Frequent Candidates
- Experimental Results
- Final Remarks
- References
- Engineering Efficient Paging Algorithms
- Introduction
- Preliminaries
- Revealed Requests
- Compressed Layers
- Engineering an Implementation for RDM
- Implementation
- Experimental Results
- References
- Feasibility Pump Heuristics for Column Generation Approaches
- Introduction
- Primal Heuristics for MIP and Feasibility Pump
- Primal Heuristics Combined with Column Generation
- A Generic Feasibility-Pump Algorithm
- Computational Results
- Conclusion
- References
- Exact Graph Search Algorithms for Generalized Traveling Salesman Path Problems
- Introduction
- Generalized Traveling Salesman Path Problems
- GTSPP Product Graphs
- Product Graph Search Using Contraction Hierarchies
- Contraction Hierarchies Overview
- Contraction Hierarchies for GTSPP
- Experiments
- Category Density
- Category Count
- Conclusion
- References
- Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach
- Introduction and Motivation
- Preliminaries
- Experimental Setup
- Summary of Experimental Results
- Discussion and Conclusions
- References
- Advanced Coarsening Schemes for Graph Partitioning
- Introduction
- Preliminaries
- Coarsening Schemes
- Coarsening
- Uncoarsening
- Experimental Evaluation
- Conclusions
- References
- A Heuristic for Non-convex Variance-Based Clustering Criteria
- Introduction
- Notation and Background
- Heuristic for Variance-Based Criteria
- Experimental Results
- Clustering Quality Analysis
- Runtime Analysis
- Summary and Future Research
- References
- A Decomposition Approach for Solving Critical Clique Detection Problems
- Introduction
- The Critical Clique Detection Problem (CCP)
- Objective Functions
- NP-Completeness of the CCP
- CCP formulations
- Decomposition Approach for Solving the CCP
- Constructing Clique Partitions
- Clique Collapsing
- CNP Generalization for Solving the CCP
- Computational Experiments
- Concluding Remarks
- References
- Author Index
