Analysis of Experimental Algorithms

Name: Analysis of Experimental Algorithms | Special Event, SEA² 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers
Brand: Springer
Price: 85.59 EUR
Availability: OnlineOnly

Special Event, SEA² 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers

Ilias Kotsireas Panos Pardalos Konstantinos E. Parsopoulos Dimitris Souravlias Arsenis Tsokas(Herausgeber*in)

Springer (Verlag)

Erschienen am 14. November 2019

XI, 564 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-34029-2 (ISBN)

85,59 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken