Experimental Algorithms
10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5-7, 2011, Proceedings
Published on 21. April 2011
X, 460 pages
978-3-642-20662-7 (ISBN)
Description
This volume constitutes the refereed proceedings of the 10th International Symposium on Experimental Algorithms, SEA 2011, held in Kolimpari, Chania, Crete, Greece, in May 2011.
The 36 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 83 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
Panos M. Pardalos | Steffen Rebennack
Experimental Algorithms
10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5-7, 2011, Proceedings
Book
04/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Table of Contents
- Experimental Algorithms and Applications
- Invited Papers
- Approximability of Symmetric Bimatrix Games and Related Experiments
- Introduction
- Preliminaries
- Approximability of NE Points via (exact) KKT Points
- Polynomial Time Construction of (13+)-NE Points
- Extension to Asymmetric Games
- Presentation of Random Games Generator and BIMATRIX-NASH Relaxations
- Pseudo-random Game Generator
- KKT Relaxation
- RLT Relaxation
- Doubly Positive Semidefinite Programming Relaxation
- Using Projections of Extreme CE Points
- Experimental Results
- Pure Relaxations
- Hybrid Relaxations
- Conclusions
- References
- Metaheuristic Optimization: Algorithm Analysis and Open Problems
- Introduction
- Convergence Analysis of Metaheuristics
- Simulated Annealing
- PSO and Convergence
- Firefly Algorithm, Convergence and Chaos
- Markov Chain Monte Carlo
- Search Efficiency and Randomization
- Gaussian Random Walks
- Randomization via Lévy Flights
- Open Problems
- References
- Contributed Papers
- Convexity and Optimization of Condense Discrete Functions
- Introduction
- Convexity and Optimization of Condense Discrete Functions
- Convexity of Condense Discrete Functions
- Optimization of Condense Discrete Functions
- An Example
- References
- Path Trading: Fast Algorithms, Smoothed Analysis, and Hardness Results
- Introduction
- Model and Notation
- Complexity Results and Smoothed Analysis
- Evaluation
- Experimental Setup
- Experimental Results
- References
- Hierarchical Delaunay Triangulation for Meshing
- Introduction
- Quality Measure
- Delaunay Triangulation and Constrained Delaunay Triangulation
- Hierarchical Delaunay Triangulation for Mesh Generation
- Mesh Size Trend for Pad Refinement
- Conclusion and Future Work
- References
- A Parallel Multi-start Search Algorithm for Dynamic Traveling Salesman Problem
- Introduction
- Multi-start Search and Solution Attractor
- The Dynamic Traveling Salesman Problem
- The Multi-start Search Procedure
- Conclusion
- References
- Online Dictionary Matching with Variable-Length Gaps
- Introduction
- Patterns with Gaps and Wildcards
- The Matching Algorithm
- Complexity
- Experimental Results
- Conclusion
- References
- Dynamic Arc-Flags in Road Networks
- Introduction
- Preliminaries
- Dynamic Arc-Flags
- Experimental Study
- Conclusions
- References
- Efficient Routing in Road Networks with Turn Costs
- Introduction
- Related Work
- Preliminaries
- Turn Cost Model
- Fixed Cost
- Turning Speed
- Node Contraction
- With Turn Costs
- Optimizations
- Preprocessing
- Query
- Turn Cost Tables
- Redundancy
- Experiments
- Conclusions
- Future Work
- References
- On Minimum Changeover Cost Arborescences
- Introduction
- Complexity
- Formulations
- Combinatorial Lower and Upper Bounds
- A Stronger Linearization
- Heuristic Algorithm
- Computational Results
- Lower Bounds on Small Instances
- Lower Bounds on Medium Size Instances
- Branch-and-Cut
- References
- Localizing Program Logical Errors Using Extraction of Knowledge from Invariants
- Introduction
- Invariants
- Related Works
- Background
- Daikon Algorithm
- Suggested Framework
- Variable Matching
- Scalability
- The Experimental Result
- Conclusion and Further Works
- References
- Compressed String Dictionaries
- Introduction
- Basic Concepts and Related Work
- Compressed Dictionary Representations
- Hashing and Compression
- Front-Coding and Compression
- FM-Index Based Representation
- Re-pair Based Representation
- XBW Trie Representation
- Experimental Results
- Final Remarks
- References
- Combinatorial Optimization for Weighing Matrices with the Ordering Messy Genetic Algorithm
- Introduction
- Applications of Periodic Complementary Sequences
- Recent Progress for Searching Weighing Matrices
- Messy Genetic Algorithms for Weighing Matrices
- An Added Level of Sophistication for Searching Weighing Matrices: OmeGA
- Design of the OmeGA
- References
- Improved Automated Reaction Mapping
- Introduction
- Background
- Graph Isomorphism
- Previous Automated Reaction Mapping Algorithms
- Improved Automated Reaction Mapping
- Fast Canonical Labeling Using Degree Neighborhoods
- Two Stage Constructive Count Vector
- Two Stage Constructive Count Vector with Name Reuse
- Two Stage Constructive Count Vector with Name Reuse and Fast Degree Neighborhood Naming
- Experimental Results
- Conclusion
- References
- An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms
- Introduction
- Algorithms
- The k-Median Problem
- Incremental k-Median
- Hierarchical k-Median
- Datasets
- Experimental Results
- The k-Median Problem
- Incremental k-Median
- Hierarchical k-Median
- Conclusions
- References
- Engineering the Modulo Network Simplex Heuristic for the Periodic Timetabling Problem
- Introduction
- PESP and Periodic Timetabling
- The Modulo Network Simplex Method
- Improving the Modulo Simplex
- Improving Runtimes: The Inner Loop
- Improving Quality: The Outer Loop
- Experiments
- Conclusion
- References
- Practical Compressed Document Retrieval
- Introduction
- Related Work
- Bitmaps and Wavelet Trees
- Grammar Compression of Bitmaps
- Grammar Compression of Wavelet Trees
- Experimental Results
- Document Listing with Frequencies
- Top-k Retrieval
- References
- Influence of Pruning Devices on the Solution of Molecular Distance Geometry Problems
- Introduction
- The Interval Branch and Prune
- Pruning Devices
- Direct Distance Feasibility (DDF)
- Torsion Angle Feasibility (TAF)
- Secondary Structure Feasibility (SSF)
- Computational Experiments
- Conclusions
- References
- An Experimental Evaluation of Treewidth at Most Four Reductions
- Introduction
- Preliminaries
- Reductions for Graphs of Treewidth at Most Three
- Reductions for Graphs of Treewidth at Most Four
- Linear Time Algorithm for Graphs of Treewidth at Most Four
- Evaluation of Treewidth at Most Four Reductions
- Preprocessing of General Graphs
- Conclusions
- References
- A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
- Introduction
- Preliminaries
- HL Overview
- Efficient HL Implementation
- Label Pruning
- Label Ordering
- Shortest Path Covers
- Label Compression
- Partition Oracle
- Index-Free Labels
- Experimental Results
- Concluding Remarks
- References
- Hierarchy Decomposition for Faster User Equilibria on Road Networks
- Introduction
- Related Work
- Problem Formulation
- Integration into Contraction Hierarchies
- Experimental Evaluation
- Conclusions
- References
- Matching in Bipartite Graph Streams in a Small Number of Passes
- Introduction
- Our Algorithmic Innovation
- Approximation Technique
- Path-BasedDAP Approximation
- Tree-Based DAP Approximation
- Experiments
- Conclusion and Future Work
- References
- Beyond Unit Propagation in SAT Solving
- Introduction
- Basic Definitions and State of the Art
- Boolean Constraint Propagation
- Related Work
- Enhancing BCP
- General Observations on Clauses and Implications
- A Matrix Based Approach
- A Convenient Alternative
- A Suitable Side Effect
- Experiments
- Conclusion
- References
- Designing Difficult Office Space Allocation Problem Instances with Mathematical Programming
- Introduction
- Outline of Previous Related Work
- Mathematical Programming Model
- Modeling Hard Constraints
- Modeling Constraints as Objectives
- Objective Function
- Test Instance Generator for OSA
- Experiments and Results
- Conclusions
- References
- Speed Dating
- Introduction
- Preliminaries
- Bipartite Speed Dating
- General Speed Dating
- Evaluation
- References
- Experimental Evaluation of Algorithms for the Orthogonal Milling Problem with Turn Costs
- Introduction
- Problem Description and Literature Overview
- An Exact Algorithm for the odmp
- An Approximation Algorithm for the odmp
- An Heuristic for odmp
- Experimental Results
- Conclusion and Future Directions
- References
- A Branch-Cut-and-Price Algorithm for the Capacitated Arc Routing Problem
- Introduction
- Mathematical Formulations
- Two-Index Formulation
- One-Index Formulation
- Set Partitioning Approach
- Column Generation
- Branch-Cut-and-Price
- Branching Rule
- Pricing
- Strong Branching
- Cut Generation
- Computational Experiments
- Conclusions and Future Research
- References
- A Biased Random Key Genetic Algorithm Approach for Unit Commitment Problem
- Introduction
- UC Problem Formulation
- Objective Function
- Constraints
- Methodology
- Decoding Procedure
- GA Configuration
- Numerical Results
- Conclusion
- References
- A Column Generation Approach to Scheduling of Periodic Tasks
- Introduction
- Previous Work
- A Column Generation Approach
- Solving the Relaxation
- Branch and Bound
- The Objective Functions
- Scheduling Periodic Tasks
- The TAN-Bus
- Improvements
- Experiments
- Generation of Random Examples
- Evaluation
- Conclusion
- References
- Fuzzy Clustering the Backward Dynamic Slices of Programs to Identify the Origins of Failure
- Introduction
- The Fuzzy-Slice Method
- Basic Definitions
- The Method Overview
- Experimental Results
- Comparison with Tarantula
- Comparison with Cooperative Bug Isolation
- Comparison with Sober
- Comparison with Sober, Bug Isolation and Tarantula
- Concluding Remarks and Future Works
- References
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Introduction
- Our Results
- Preliminaries
- Degeneracy
- The Algorithm of Tomita et al.
- The Algorithm of Eppstein, Löffler, and Strash
- Tomita et al. with Adjacency Lists
- Implementation and Experiments
- Implementation Details
- Results
- Conclusion
- References
- Customizable Route Planning
- Introduction
- Previous Techniques
- Our Approach
- Turns
- Conclusion
- References
- Efficient Algorithms for Distributed Detection of Holes and Boundaries in Wireless Networks
- Introduction
- Model Description
- Network Model
- Hole and Boundary Model
- Multidimensional Scaling Boundary Recognition (MDS-BR)
- Enclosing Circle Boundary Recognition (EC-BR)
- Simulations
- Simulation Setup
- Network Density
- Random Placement vs. Perturbed Grid
- Beyond Unit Disk Graphs
- Visual Comparison
- Conclusion
- References
- Explanations for the Cumulative Constraint: An Experimental Study
- Introduction
- Cumulative Scheduling
- Propagation and Explanation Algorithms
- Energetic Reasoning
- Edge-Finding
- Time-Tabling
- Experimental Study
- Computational Environment
- Computational Results
- Conclusions
- References
- GRASP with Path-Relinking for Data Clustering: A Case Study for Biological Data
- Introduction
- GRASP with Path-Relinking for Data Clustering
- Path-Relinking
- Experimental Results
- Datasets
- Test Environment and Parameters for GRASP-PR Heuristic
- Numerical Comparisons
- Concluding Remarks
- References
- An Iterative Refinement Algorithm for the Minimum Branch Vertices Problem
- Introduction
- Iterative Refinement and Constrained Spanning Trees
- An Iterative Refinement Algorithm for the MBV Problem
- Experimental Results
- Concluding Remarks
- References
- Generating Time Dependencies in Road Networks
- Introduction
- Analysis of Real-World Time-Dependent Data
- Algorithms for Assigning Profiles
- Algorithm I: Affected-By-Category
- Algorithm II: Affected-By-Region
- Algorithm III: Affected-By-Level
- Experiments
- Conclusion
- References
- An Empirical Evaluation of Extendible Arrays
- Introduction
- Data Structures
- Experimental Evaluation
- Implementation Details
- Speed Tests
- Memory Usage Results
- Conclusions
- References
- Author Index
