Experimental Algorithms 13th International Symposium SEA 2014 Copenhagen Denmark June 29 July 1 2014 Proceedings 1st Edition by Joachim Gudmundsson, Jyrki Katajainen 3319079592 9783319079592

Experimental Algorithms 13th International Symposium SEA 2014 Copenhagen Denmark June 29 July 1 2014 Proceedings 1st Edition by Joachim Gudmundsson, Jyrki Katajainen – Ebook PDF Instant Download/DeliveryISBN:  3319079592, 9783319079592  

Full download Experimental Algorithms 13th International Symposium SEA 2014 Copenhagen Denmark June 29 July 1 2014 Proceedings 1st Edition after payment.

Product details:

ISBN-10 :  3319079592 

ISBN-13 :  9783319079592

Author:  Joachim Gudmundsson, Jyrki Katajainen 

This book constitutes the refereed proceedings of the 13th International Symposium on Experimental Algorithms, SEA 2014, held in Copenhagen, Denmark, in June/July 2014. The 36 revised full papers presented together with 3 invited presentations were carefully reviewed and selected from 81 submissions. The papers are organized in topical sections on combinatorial optimization, data structures, graph drawing, shortest path, strings, graph algorithms and suffix structures.

Experimental Algorithms 13th International Symposium SEA 2014 Copenhagen Denmark June 29 July 1 2014 Proceedings 1st Table of contents:

Selecting Data for Experiments: Past, Present and Future
1 Introduction
2 Encapsulating the Past
2.1 Sorting I
3 Learning from the Present
3.1 Sorting II
3.2 Geometric Point Sets I
4 Predicting the Future
4.1 A Simple and Safe Bet
4.2 Geometric Point Sets II
4.3 Data Compression Using Long Common Strings
5 Conclusions
References
Combinatorial Optimization
The Hospitals / Residents Problem with Couples: Complexity and Integer Programming Models
1 Introduction
2 Complexity Results
3 An IP Formulation for HRC
4 Empirical Results
References
Integral Simplex Using Decomposition with Primal Cuts
1 Introduction
1.1 The Set Partitioning Problem
1.2 Primal Algorithms
1.3 Objectives and Contributions
2 An Integral Simplex for SPP
2.1 Relaxing the Integrality Constraints
2.2 Taking Integrality into Account
2.3 Algorithmic Framework
3 Solving RC-MRA with Cutting Planes
3.1 Theory and Generic Cutting-Plane Procedure
3.2 Primal Clique Cut Separation: Q-P-SEP
4 Experimentation
4.1 Algorithm and Instances
4.2 Numerical Results
5 Conclusions and Future Work
References
A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs
1 Introduction
2 Formulations and Properties
2.1 Compact Formulation
2.2 Extended Formulation
3 Algorithmic Ingredients
3.1 Solving the Pricing Problem
3.2 Branching
3.3 Cutting Planes
3.4 Combinatorial Dual Bounds
3.5 Primal Heuristics
4 Computational Setup and Results
4.1 Compact vs. Extended Formulation
4.2 Different Graph Classes
4.3 Influence of Particular Implementation Parts
4.4 Relation to Independent Set
5 Summary and Conclusions
References
Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth
1 Introduction
1.1 Practical Computation of Pathwidth
1.2 Contributions and Organization of the Paper
2 Preliminaries
2.1 Definitions and Notations
2.2 Technical Lemmas for Preprocessing
2.3 Technical Lemmas for the Pruning Part
3 The Algorithm
3.1 Pre-processing Phase
3.2 Branch & Bound Phase
4 Simulations and Interpretation of Results
4.1 Implementation
4.2 Evaluation in Random Digraphs
4.3 Comparison of BAB-GPP with SAT on Rome Graphs
4.4 Impact of Prefix Length
4.5 Using BAB-GPP as an Heuristic
5 Conclusion
References
An Exact Algorithm for the Discrete Chromatic Art Gallery Problem
1 Introduction
2 Terminology and Problem Statement
3 An Integer Programming Formulation for the DCAGP
4 Implementation Details
5 Computational Results
6 Conclusion and Future Directions
References
Implementation of the Iterative Relaxation Algorithm for the Minimum Bounded-Degree Spanning Tree Pr
1 Introduction
2 The Iterative Relaxation Algorithm
2.1 The Algorithm
3 Local Search
4 Experimental Results
4.1 Test Cases
4.2 Comparison of IR and SA
References
Relocation in Carsharing Systems Using Flows in Time-Expanded Networks
1 Introduction
2 Problem Description and Model
3 Flows in Time-Expanded Networks
3.1 Time-Expanded Networks
3.2 A Max-Profit Flow Problem
4 A Flow-Based Heuristic
4.1 Preprocessing (Phase 1)
4.2 Computing a Transportation Schedule (Phase 2)
4.3 Improving the Solution
5 Computational Results and Conclusions
References
Dynamic Windows Scheduling with Reallocation
1 Introduction
2 Related Work
3 Model
4 Our Contributions
5 Preemptive Reallocation and Lazy Reallocation Algorithms
6 Classified Reallocation
7 Simulations
References
Data Structures
Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates
1 Introduction
2 Preliminaries and Related Work
2.1 Sequential Multi-objective Search
2.2 Parallel Search Trees
3 Parellel Bi-objective Search
3.1 A B-tree Based Pareto Queue
3.2 Parallel Bi-objective Search
4 Experimental Evaluation
4.1 Pareto Queue Evaluation
4.2 Parallel Bi-objective Search
5 Conclusion
References
Beyond Synchronous: New Techniques for External-Memory Graph Connectivity and Minimum Spanning Fores
1 Introduction
2 Related Work
3 Preliminaries
4 Minimum Label Propagation
5 Minimum Spanning Forest and Graph Contraction
6 Experiments
7 Conclusion
References
Retrieval and Perfect Hashing Using Fingerprinting
1 Introduction
2 Preliminaries
3 Related Work
4 Retrieval Using Fingerprint Hashing
4.1 The FiRe Data Structure
4.2 Choosing Parameters
4.3 Dynamization
5 Fingerprint Based Perfect Hashing (FiPHa)
6 Experiments
7 Conclusion
References
Efficient Wavelet Tree Construction and Querying for Multicore Architectures
1 Introduction and Motivation
2 Preliminaries
3 Multicore Wavelet Tree
4 Experimental Results
5 Conclusion
References
Wear Minimization for Cuckoo Hashing:How Not to Throw a Lot of Eggs into One Basket
1 Introduction
1.1 Wear Leveling in Modern Memories
1.2 Related Work
1.3 Our Results
2 Algorithm
3 Analysis
4 Experiments
4.1 Discussion
References
Loop Nesting Forests, Dominators, and Applications
1 Introduction
2 Loop Nesting Forests
3 Dominators
4 Connectivity and Related Applications
5 Concluding Remarks
References
DenseZDD:A Compact and Fast Index for Families of Sets
1 Introduction
2 Preliminaries
2.1 Zero-Suppressed Binary Decision Diagrams (ZDDs)
2.2 Problem of Existing ZDDs
3 Data Structure
3.1 DenseZDD
4 Algorithm
4.1 Conversion of an Ordinary ZDD to a DenseZDD
4.2 Primitive ZDD Operations
4.3 Compressing the Balanced Parentheses Sequence
5 Hybrid Method
6 Experimental Results
7 Conclusion
References
An Evaluation of Dynamic Labeling Schemes for Tree Networks
1 Introduction
1.1 Preliminaries
2 Dynamic Labeling Schemes for Tree Networks
2.1 Brief Overview
3 Experimental Framework
4 Experimental Results
4.1 SemGL
4.2 Comparison of SemGL and SemDL
4.3 Fully-Dynamic Labeling Schemes
5 Conclusions
References
Graph Drawing
Engineering Color Barcode Algorithms for Mobile Applications
1 Introduction
2 Experimental Setup
3 Color Classification in Desktop and Mobile Scenarios
4 Force-Directed Graph Drawing Algorithms
4.1 First Phase
4.2 Second Phase
5 Experimental Results
References
Computing Consensus Curves
1 Introduction
2 The Local Approach
3 The Global Approach
4 The SIMULTANEOUS CONSENSUS PATHS Problem
5 Experimental Results
6 Conclusions and Future Work
References
Evaluation of Labeling Strategies for Rotating Maps
1 Introduction
2 Preliminaries
3 Algorithmic Approaches
3.1 Greedy Heuristics
3.2 Integer Linear Program
4 Experimental Evaluation
4.1 Benchmark Instances
4.2 Evaluation of the Consistency Models
4.3 Evaluation of the Algorithms
5 Conclusion
References
Experimental Comparison of Semantic Word Clouds
1 Introduction
2 Experimental Setup
3 Word Cloud Layout Algorithms
4 Metrics for Evaluating Word Cloud Layouts
5 Results and Discussion
6 Conclusions and Future Work
References
Shortest Path
Hub Labels: Theory and Practice
1 Introduction
2 Preliminaries
3 Approximation Algorithms
3.1 Optimizing Arbitrary Norms
4 Improved Time Bound
4.1 Practical Improvement
5 Experiments
6 Concluding Remarks
References
Customizable Contraction Hierarchies
1 Introduction
2 Basics
3 Phase 1: Preprocessing the Graph Topology
4 Phase 2: Customizing the Metric
5 Phase3:At Query Time
6 Comparison with CRP
7 Experiments
8 Conclusions
References
Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches
1 Introduction
2 Implemented Algorithms
3 Experimental Setup
4 Analysis
References
Exploiting GPS Data in Public Transport Journey Planners
1 Introduction
2 Preliminaries
3 Journey Planners Considered in Our Experiments
4 GPS Data Processing and Simulation System
5 Experiments and Discussion
5.1 Analysis of Bus Trips
5.2 Accuracy of Estimates
5.3 Quality of Solutions
6 Conclusions and Future Work
References
Strings
Order-Preserving Matching with Filtration
1 Introduction
2 Previous solutions
3 Our Solution
4 Analysis
5 Experiments
6 Concluding Remarks
References
Approximate Online Matching of Circular Strings
1 Introduction
2 CBNDM
3 New Algorithms
4 Analysis
5 Experiments
6 Concluding Remarks
References
From Theory to Practice:Plug and Play with Succinct Data Structures
1 Introduction
2 Document Retrieval Recomposed
2.1 SADA and GREEDY Revisited
2.2 Experimental Setup
2.3 Plug and Play
3 Efficient Construction of Complex Structures
4 Related Work
5 Conclusion
References
Improved ESP-index: A Practical Self-index for Highly Repetitive Texts
1 Introduction
2 Preliminaries
2.1 Grammar-Based Compression
2.2 Phrase and Reverse Dictionaries
2.3 Rank/Select Dictionaries
3 ESP-index
3.1 Edit-Sensitive Parsing (ESP)
3.2 Algorithms
4 ESP-index-I
5 Experiments
5.1 Setups
5.2 Results on Benchmark Data
5.3 Results on Large-Scale Repetitive Texts
6 Conclusion
References
Graph Algorithms
Partitioning Complex Networks via Size-Constrained Clustering
1 Introduction
2 Preliminaries
2.1 Basic Concepts
2.2 Related Work
3 Cluster Contraction
3.1 Label Propagation with Size Constraints
4 Algorithmic Extensions
5 Experiments
5.1 Main Results and Comparison to Other Partitioning Packages
5.2 Huge Web Graphs
6 Conclusion and Future Work
References
Tree-Based Coarsening and Partitioning of Complex Networks
1 Introduction
2 State of the Art
3 Preliminaries
4 Greedy MCV Optimization
5 A New Conductance-Based Edge Rating for Partitioning
6 An O(|E|)-Algorithm for Computing All cond(eT, T)
7 Experimental Results
8 Conclusions and Future Work
References
Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks
1 Introduction
2 Preliminaries
3 Description of the Algorithm Framework
3.1 General Framework Description
3.2 Phase 1: Exact k-Anonymization of Degree Sequences
3.3 Phase 2: Realizing a k-Anonymous Degree Sequence
4 Experimental Results
5 Conclusion
References
Search Space Reduction through Commitments in Pathwidth Computation: An Experimental Study
1 Introduction
2 Preliminaries
3 Commitments
4 Experiments
4.1 Algorithm
4.2 Oracles
4.3 Search Space Reduction
4.4 Performance of the Algorithm with Depth-1 Commitments
4.5 Comparisons between the Pathwidth and the Treewidth
5 Conclusion
References
Suffix Structures
Efficient Representation for Online Suffix Tree Construction
1 Introduction
2 Suffix Trees and Ukkonen’s Algorithm
3 Reduced Branching Schemes
3.1 Node-Oriented Bottom-Up
3.2 Edge-Oriented Top-Down
3.3 Edge-Oriented Variable
4 Branching Data Structure
5 Performance Evaluation on Input Corpora
5.1 Models, Measures, and Data
5.2 Results
6 Conclusion
References
LCP Array Construction in External Memory
1 Introduction
2 Preliminaries
3 Basic Algorithm
4 Irreducible LCP Values
5 Practical Improvements
6 Experimental Results
References
Faster Compressed Suffix Trees for Repetitive Text Collections
1 Introduction
2 Basic Concepts
2.1 Succinct Tree Representations
2.2 Compressed Suffix Trees
2.3 Grammar Compression of Strings and Trees
3 A New CST for Repetitive Text Collections
4 Experimental Results and Discussion
References
Improved and Extended Locating Functionality on Compressed Suffix Arrays
1 Introduction
2 Compressed Suffix Arrays
3 A Combined Structure for Locating and Displaying
4 A Structure for Prioritized Location of Occurrences
5 Range-Restricted Location of Occurrences
6 Experimental Results

People also search for Experimental Algorithms 13th International Symposium SEA 2014 Copenhagen Denmark June 29 July 1 2014 Proceedings 1st:

symposium on experimental algorithms
    
symposium on experimental algorithms 2025
    
journal of experimental algorithms
    
international symposium on experimental algorithms 2025
    
symposium on experimental algorithms sea

Tags: Experimental Algorithms, International Symposium, Copenhagen Denmark, Proceedings, Joachim Gudmundsson, Jyrki Katajainen