
Analysis of Experimental Algorithms
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
The 35 revised full papers presented were carefully reviewed and selected from 45 submissions. The papers cover a wide range of topics in both computer science and operations research/mathematical programming. They focus on the role of experimentation and engineering techniques in the design and evaluation of algorithms, data structures, and computational optimization methods.
More details
Other editions
Additional editions

Content
- Intro
- Preface
- Organization
- Contents
- Voronoi Diagram of Orthogonal Polyhedra in Two and Three Dimensions
- 1 Introduction
- 2 Basic Definitions and Properties
- 3 Subdivision Algorithm in Two Dimensions
- 3.1 Subdivision Phase
- 3.2 Reconstruction Phase
- 3.3 Primitives, Data-Structures, Complexity
- 4 Subdivision Algorithm in Three Dimensions
- 5 Implementation and Concluding Remarks
- References
- The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation
- 1 Introduction
- 2 Preliminaries
- 3 Contraction-Minimal Representations
- 3.1 Chordal Graph Generation in Linear Time
- 3.2 Experimental Studies
- 4 Arbitrary Representations
- 5 Conclusion
- References
- Computing a Minimum Color Path in Edge-Colored Graphs
- 1 Introduction
- 1.1 Our Contribution
- 2 Hardness of Approximation
- 3 An O(n2/3)- Approximation Algorithm
- 4 Fast Heuristic Algorithms and Datasets
- 4.1 Min-color Path in Uniformly Colored Random Graphs
- 4.2 Constructing Hard Instances
- 4.3 ILP Formulation
- 4.4 Greedy Strategies
- 4.5 Experiments and Results
- 5 Conclusion
- References
- Student Course Allocation with Constraints
- 1 Introduction
- 2 Algorithm Description
- 2.1 Iterative Algorithm Framework
- 2.2 Gale-Shapley Algorithm in the Iterative Algorithm Framework
- 2.3 First Preference Allotment in the Iterative Algorithm Framework
- 2.4 Extending the Iterative Algorithm Framework to additionally allow downward feasible constraints for courses
- 3 Theoretical Guarantees
- 3.1 Characterization of Pareto Optimality in the Many-to-Many Setting
- 3.2 Proof of Pareto Optimality from the Student Side
- 3.3 Time Complexity
- 4 Evaluation Metrics
- 4.1 Mean Effective Average Rank
- 4.2 Other Metrics
- 5 Experimental Results
- 5.1 Input Data Generator
- 5.2 Effect of Varying Instance Size
- 5.3 Effect of Increasing Competition
- 5.4 Effect of Varying Preference List Sizes
- 5.5 Discussion
- 6 Conclusion
- References
- A Combinatorial Branch and Bound for the Min-Max Regret Spanning Tree Problem
- 1 Introduction
- 2 A Framework for a Branch and Bound
- 2.1 A Lower Bound
- 2.2 An Upper Bound
- 3 A Combinatorial Branch and Bound Algorithm
- 4 Numerical Experiments
- 4.1 Effect of Pruning
- 4.2 Effect of Edge Density and Number of Scenarios
- 4.3 Comparison with the Approach in ch5minspsmaxspspseudo
- 5 Discussion and Conclusion
- References
- Navigating a Shortest Path with High Probability in Massive Complex Networks
- 1 Introduction
- 1.1 Related Works
- 1.2 Our Methods
- 1.3 Outlines
- 2 Preliminary
- 3 Algorithm Description
- 3.1 Navigator
- 3.2 Navigation Algorithms
- 4 Experiments
- 4.1 Datasets and Environment Description
- 4.2 Evaluation Metrics
- 4.3 Analysis
- 5 Conclusion
- References
- Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs
- 1 Introduction
- 1.1 Case Study: Feedback Vertex Set
- 2 Preliminaries
- 2.1 Balanced Separator
- 2.2 Kernelization Algorithm
- 3 Corrected Reduction Rule
- 4 Polynomial-Time Approximation Scheme
- 5 Engineering Considerations
- 5.1 Kernelization Algorithm
- 5.2 Balanced Separators
- 5.3 Heuristics
- 6 Experimental Results
- 6.1 Runtime
- 6.2 Solution Quality
- 6.3 Effects of Parameters on Performance
- 7 Conclusions
- References
- On New Rebalancing Algorithm
- 1 Introduction
- 2 qBalance Algorithm Over Binary Search Tree. The Comparison with DSW Algorithm
- 3 qBalance Algorithm over Ordered Search Tree (OST). The Comparison with Sedgewick Algorithm
- 4 qBalance Algorithm Over Doublestructured RB Tree. The Comparison with the Modified Sedgewick Algorithm
- 5 qBalane Algorithm for Standard RB Tree. The Comparison Between Sequential and Parallel (Two Threads) Implementations
- 6 Conclusion
- References
- Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs
- 1 Introduction
- 2 Preliminaries
- 2.1 Forbidden Induced Subgraphs and Chordal and Interval Graphs
- 2.2 Multi-valued Decision Diagrams
- 2.3 Frontier-Based Search
- 3 Graph Classes Constructed by Colorful Frontier-Based Search
- 3.1 Colorful FBS for Colored Degree Specified Graphs
- 3.2 Coloring Graphs in X31, XF21 and XF30
- 3.3 Decolorization
- 4 Induced Subgraph and FIS-Characterization
- 4.1 Colorful FBS for Edge-Inducing
- 4.2 Recursive Algorithm
- 4.3 2-DDs for Interval and Proper Interval Subgraphs
- 5 Experiments
- 6 Conclusion
- References
- Unit Disk Cover for Massive Point Sets
- 1 Introduction
- 2 Algorithms
- 2.1 HM-1985: Hochbaum and Mass (1985)
- 2.2 G-1991: Gonzalez (1991)
- 2.3 CCFM-1997: Charikar, Chekuri, Feder, and Motwani (1997)
- 2.4 FCB-2001: Franceschetti, Cook, and Bruck (2001)
- 2.5 LL-2014: Liu and Lu (2014)
- 2.6 BLMS-2017: Biniaz, Liu, Maheshwari, and Smid (2017)
- 2.7 DGT-2018: Dumitrescu, Ghosh, and Tóth (2018)
- 2.8 GHS: A Fast 7-Approximation Algorithm
- 3 Experimental Results
- 4 Conclusion
- References
- Improved Contraction Hierarchy Queries via Perfect Stalling
- 1 Introduction
- 1.1 Contribution and Outline
- 2 Preliminaries
- 2.1 Contraction Hierarchies
- 2.2 CH-Based Hub Labels
- 3 Perfect Stalling
- 3.1 Precomputing Perfect Stalling Decisions
- 4 Experiments
- 4.1 Data Sets, CH and HL Precomputation
- 4.2 Stalling Trace Construction
- 4.3 Queries
- 5 Conclusion
- References
- Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
- 1 Introduction and Related Work
- 2 Constraint Generation Algorithm for MCI
- 2.1 Presentation
- 2.2 Choice of Cuts
- 3 Experimental Evaluation
- 3.1 Generation of Instances
- 3.2 Comparison with the Flow-Based MILP Formulation
- 4 Enumeration Algorithm
- 5 Conclusion
- References
- Efficient Split-Radix and Radix-4 DCT Algorithms and Applications
- 1 Introduction
- 2 Simple, Self-recursive, Split-Radix and Radix-4 DCT Algorithms
- 2.1 Frequently Use Notations
- 2.2 Self-enclosed, Sparse, and Scaled Orthogonal Factors for DCT II/III
- 2.3 Self Recursive Split-Radix and Radix-4 DCT II/III Algorithms
- 3 Complexity of the Proposed DCT II/III Algorithms
- 3.1 Arithmetic Complexity of Self-recursive Split-Radix and Radix-4 DCT II/III Algorithms
- 3.2 Complexity Comparison of DCT II/III Algorithms
- 3.3 Performance and Execution Time of the Split-Radix and Radix-4 DCT Algorithms
- 4 Signal Flow Graphs for Split-Radix and Radix-4 DCT II/III Algorithms
- 5 Conclusion
- References
- Analysis of Max-Min Ant System with Local Search Applied to the Asymmetric and Dynamic Travelling Salesman Problem with Moving Vehicle
- 1 Introduction
- 2 Related Work
- 3 Problem Formulation and Modeling
- 3.1 The Asymmetric and Dynamic Travelling Salesman Problem with Moving Vehicle (ADTSPMV)
- 3.2 Max-Min Ant System (MMAS)
- 3.3 MMAS with Local Search
- 3.4 MMAS with Memory
- 4 Protocol of Experiments, Results and Analysis
- 4.1 ADTSP Results
- 4.2 ADTSPMV Results
- 5 Conclusions and Future Work
- References
- Computing Treewidth via Exact and Heuristic Lists of Minimal Separators
- 1 Introduction
- 2 Preliminaries
- 3 Dynamic Programming for Tree-Decompositions with a Given Set Of available Minimal Separators
- 4 Listing Minimal Separators
- 4.1 A Minimal a-b Separator Algorithm
- 4.2 Nibble and Conquer
- 4.3 Heuristic Listing of Minimal Separators
- 5 Treewidth Algorithms
- 6 Experimental Results
- 6.1 Graph Instances
- 6.2 Minimal Separator Listing Algorithms
- 6.3 Treewidth Algorithms
- References
- Fast Public Transit Routing with Unrestricted Walking Through Hub Labeling
- 1 Introduction
- 2 Preliminaries
- 3 HLRaptor: RAPTOR with Two-Hop Transfers
- 4 HLCSA: Connection Scan with Two-Hop Transfers
- 5 Public Transit Data
- 6 Experiments
- 7 Conclusion
- References
- Effective Heuristics for Matchings in Hypergraphs
- 1 Introduction
- 2 Background and Notation
- 3 Heuristics for Maximum d-Dimensional Matching
- 3.1 A Greedy Heuristic for Max-d-DM
- 3.2 Karp-Sipser for Max-d-DM
- 3.3 Karp-Sipser-scaling for Max-d-DM
- 3.4 Hypergraph Matching via Pseudo Scaling
- 3.5 Reduction to Bipartite Graph Matching
- 3.6 Performing Local Search
- 4 Experiments
- 4.1 Experiments on Random Hypergraphs
- 4.2 Evaluating Algorithmic Choices
- 4.3 Experiments with Real-Life Tensor Data
- 4.4 Experiments with an Independent Set Solver
- 5 Conclusion and Future Work
- References
- Approximated ZDD Construction Considering Inclusion Relations of Models
- 1 Introduction
- 2 Related Work
- 3 Preliminaries
- 3.1 Zero-Suppressed Binary Decision Diagrams
- 3.2 False Positives/False Negatives
- 4 Approximation of a Given ZDD
- 4.1 Node Merging Without False Negatives
- 4.2 Finding All Inclusion Relations in Each Layer
- 4.3 Finding Inclusion Relations Under Monotonicity
- 4.4 Greedy Reduction by Selecting Nodes to Be Incorporated
- 5 On-the-Fly Approximation in the Construction of a ZDD
- 5.1 ZDD Construction by Depth-First Dynamic Programming
- 5.2 Approximated Construction in Depth-First Manner
- 6 Experiments and Results
- 6.1 Approximation of a Given ZDD
- 6.2 On-the-Fly Approximation
- 7 Conclusion
- A Speeding Up Finding Inclusion Relations Under Monotonicity
- References
- Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
- 1 Introduction
- 1.1 Related Work
- 1.2 Basic Definitions
- 2 Algorithm Description
- 2.1 Idea of the Algorithm
- 2.2 Initial Algorithm Modification
- 2.3 Further Implementation Optimizations
- 3 Experimental Results
- 3.1 Algorithm Properties and Performance
- 3.2 Comparison on Real World Graphs and Fixed Graph Patterns
- 3.3 ICPR2014 Contest Graphs
- 3.4 Erdos-Rényi Graph Setup
- 4 Conclusion
- References
- Quantum-Inspired Evolutionary Algorithms for Covering Arrays of Arbitrary Strength
- 1 Introduction
- 2 Evolutionary Algorithms and Quantum Computing
- 3 A Quantum-Inspired Evolutionary Algorithm for CAs
- 3.1 Simplified Qubit-Representation
- 3.2 Algorithmic Description
- 4 Experimental Results
- 4.1 Parameter Tests for Rotation and Mutation
- 4.2 Algorithm Evaluation
- 5 Conclusion and Future Work
- References
- An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model
- 1 Introduction
- 2 The Four Shortest-Path Algorithms
- 2.1 The Classic Algorithm by Lee and Preparata
- 2.2 Using Constrained Delaunay-Triangulations
- 2.3 Using Trapezoidal Decompositions
- 2.4 The Makestep Algorithm
- 3 Our Implementation
- 3.1 General Implementation Details
- 3.2 Implementing the Algorithm by Lee and Preparata
- 3.3 Implementing Delaunay and Trapezoid
- 3.4 Implementing Makestep
- 4 Experimental Setup
- 4.1 Generating the Test Instances
- 4.2 Executing the Tests
- 4.3 Test Environment
- 5 Experimental Results
- 6 Conclusion
- A Tables of Experimental Results
- References
- Searching for Best Karatsuba Recurrences
- 1 Introduction
- 2 Finding Minimum-Size Spanning Bilinear Forms
- 2.1 Description of the Problem
- 2.2 Method for Finding Spanning Sets of Bilinear Forms
- 3 Finding Small Circuits for the Linear Maps Determined by each Bilinear Form
- 4 Experimental Results
- 4.1 6-way Split
- 4.2 7-way Split
- 4.3 8-way Split
- 5 Implications for the Circuit Complexity of Binary Polynomial Multiplication
- References
- Minimum and Maximum Category Constraints in the Orienteering Problem with Time Windows
- 1 Introduction
- 2 Previous Work
- 3 Problem Formalization
- 4 Algorithmic Approaches
- 4.1 Iterated Local Search
- 4.2 Supervised Learning Iterated Local Search
- 4.3 Replace-Based Local Search
- 4.4 IP Solutions
- 5 Experimental Results
- 5.1 Datasets
- 5.2 Unconstrained Setting
- 5.3 Constrained Setting
- 6 Conclusion and Future Work
- References
- Internal Versus External Balancingpg in the Evaluation of Graph-Based Number Types
- 1 Introduction
- 2 Concepts
- 2.1 Graph Restructuring
- 2.2 Error Bound Balancing
- 3 Experiments
- 3.1 List-Like Expression Dags
- 3.2 Blocking Nodes
- 3.3 Balanced Expression Dags
- 3.4 Common Subexpressions
- 3.5 A Note on Floating-Point Primitives
- 4 Conclusion
- References
- Hacker's Multiple-Precision Integer-Division Program in Close Scrutiny
- 1 Introduction
- 2 Long-Division Algorithm
- 2.1 Software Stack
- 2.2 Algorithm Description
- 2.3 Asymptotic Analysis
- 3 Implementation
- 3.1 Function is_less
- 3.2 Function difference
- 3.3 Function product
- 3.4 Main Loop
- 4 Meticulous Analysis
- 5 Integration with the Library
- 6 Benchmarking
- 6.1 Computing Environment
- 6.2 Small Numbers
- 6.3 Large Numbers
- 7 Final Remarks
- References
- Assessing Algorithm Parameter Importance Using Global Sensitivity Analysis
- 1 Introduction
- 2 Experimental Setup
- 2.1 Non-dominated Sorting Genetic Algorithm III (NSGA-III)
- 2.2 Multi-objective Evolutionary Algorithm Based on Decomposition (MOEA/D)
- 2.3 Metrics
- 2.4 Sensitivity Analysis Techniques
- 2.5 The Problems
- 2.6 The Design Automation Framework
- 3 Results
- 4 Conclusions
- References
- A Machine Learning Framework for Volume Prediction
- 1 Introduction
- 1.1 Polytopes
- 1.2 Our Goal and Structure of the Paper
- 2 Description of the Models
- 2.1 Encoding a Polytope
- 2.2 The Problems
- 2.3 Modular Vs End-to-End
- 2.4 The Models
- 3 Description of Data
- 3.1 Normalization
- 4 Experimental Results
- 4.1 Comparison of the Models
- 5 Conclusion
- References
- Faster Biclique Mining in Near-Bipartite Graphs
- 1 Introduction
- 2 Preliminaries
- 2.1 Related Work
- 2.2 Notation and Terminology
- 3 Algorithms
- 3.1 MIB Algorithm Framework
- 3.2 Enum-MIB
- 3.3 OCT-MIB-II
- 3.4 OCT-MICA
- 4 Implementation
- 4.1 Algorithm Framework
- 4.2 MICA
- 5 Experiments
- 5.1 Data and Experimental Setup
- 5.2 Initial Benchmarking
- 5.3 Larger Graphs
- 5.4 Computational Biology Data
- 6 Conclusion
- A MIB-Enumeration Framework Subroutines
- A.1 MakeIndMaximal
- A.2 AddTo
- B MB-Enumeration Framework Subroutines
- B.1 MakeMaximal
- B.2 Consensus
- C Additional Enumeration Experiments
- References
- k-Maximum Subarrays for Small k: Divide-and-Conquer Made Simpler
- 1 Introduction
- 2 Previous Work
- 3 k-Maximum Subarrays by Divide and Conquer
- 4 An Improved Algorithm for k-Maximum Subarrays
- 5 Implementation and Experiments
- 6 Conclusion
- References
- A Faster Convex-Hull Algorithm via Bucketing
- 1 Introduction
- 2 Bucketing
- 3 Micro-benchmarking
- 4 Competitors
- 5 Experiments
- 6 Reflections
- References
- Fixed Set Search Applied to the Minimum Weighted Vertex Cover Problem
- 1 Introduction
- 2 Greedy Algorithm
- 3 Local Searches
- 3.1 Element Swap
- 3.2 Pair Swap
- 3.3 Local Search
- 4 GRASP
- 5 Fixed Set Search
- 5.1 Fixed Set
- 5.2 Learning Mechanism
- 6 Results
- 7 Conclusion
- References
- Automated Deep Learning for Threat Detection in Luggage from X-Ray Images
- Abstract
- 1 Introduction
- 2 Threat Identification Framework
- 3 Experimentation and Results
- 4 Conclusion
- References
- Algorithmic Aspects on the Construction of Separating Codes
- 1 Introduction
- 2 Definitions and Previous Results
- 2.1 Separating Codes
- 2.2 Algorithmic Lovász Local Lemma
- 3 A Lower Bound on the Rate of 2-Separating Binary Codes
- 4 Explicit Constructions
- 4.1 Direct Application of the Algorithmic LLL for Constructing 2-Separating Codes
- 4.2 Constructions of Polynomial Complexity
- 5 Conclusions
- References
- Lagrangian Relaxation in Iterated Local Search for the Workforce Scheduling and Routing Problem
- 1 Introduction
- 2 Problem Description
- 3 Xie-Potts-Bektas Algorithm
- 4 Lagrangian Relaxation Based Modification of the Xie-Potts-Bektas Algorithm
- 5 Computational Experiment
- 5.1 Setting of the Algorithms
- 5.2 Evaluation of Different Step Length
- 5.3 Comparison of the Performance
- 6 Conclusion
- References
- Approximation Algorithms and an Integer Program for Multi-level Graph Spanners
- 1 Introduction
- 1.1 Multi-level Graph Spanners
- 1.2 Related Work
- 2 Approximation Algorithms for MLGS
- 2.1 Oracle Bottom-Up Approach
- 2.2 Oracle Top-Down Approach
- 2.3 Combining Top-Down and Bottom-Up
- 2.4 Heuristic Subsetwise Spanners
- 3 Integer Linear Programming (ILP) Formulations
- 3.1 ILP Formulation for the MLGS Problem
- 3.2 Size Reduction Techniques
- 4 Experimental Results
- 4.1 Setup
- 4.2 Results
- 5 Discussion and Conclusion
- A Proof of Theorem 4
- B Proof of Theorem 6
- C Proof of Theorem7
- D Experimental Results on Graphs Generated Using Watts-Strogatz
- E Experimental Results on Large Graphs Using Erdos-Rényi
- References
- Author Index
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.