Theory and Practice of Algorithms in (Computer) Systems
First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, Proceedings
Published on 29. March 2011
X, 266 pages
978-3-642-19754-3 (ISBN)
Description
This book constitutes the refereed proceedings of the First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011, held in Rome, Italy, in April 2011. The 25 papers presented, including three short papers by invited speakers, were carefully reviewed and selected from 45 submissions. The papers all feature original research in the design, implementation and evaluation of algorithms with special focus on algorithms for combinatorial optimization problems, and to real-world applications, engineering and experimental analysis of algorithms - thus fostering the cooperation among researchers in computer science, networking, discrete mathematics, mathematical programming and operations research.
More details
Other editions
Additional editions
Alberto Marchetti-Spaccamela | Michael Segal
Theory and Practice of Algorithms in (Computer) Systems
First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, Proceedings
Book
03/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Distributed Decision Problems: The Locality Angle
- Introduction
- Distributed Verification
- References
- Managing Power Heterogeneity
- References
- The Mathematics of Mobility
- References
- Speed Scaling to Manage Temperature
- Introduction
- Batched Release
- Known Maximum Temperature
- Unknown Maximum Temperature
- Online Algorithm
- Additional Results
- References
- Alternative Route Graphs in Road Networks
- Introduction
- Related Work
- Alternative Graphs
- Attributes to Measure in AGs
- Methods to Compute Alternatives
- k-Shortest Paths
- Pareto
- Plateau
- Penalty
- Combinations
- Refinements / Post Processing
- Different Edge Weights
- Experiments
- User Study
- Conclusion and Outlook
- References
- Robust Line Planning in Case of Multiple Pools and Disruptions
- Introduction
- Multiple Line Pools: Different Utilities per Pool
- Experimental Study of the Multiple-Line Pool Cases
- Experimental Study of Disruptions in the Network
- Conclusions
- References
- Exact Algorithms for Intervalizing Colored Graphs
- Introduction
- Preliminaries
- Partial Path Decompositions
- An Exact Algorithm for Intervalizing k-Colored Graphs
- An Algorithm for Intervalizing Colored Graphs with an Arbitrary Number of Colors
- Conclusions
- References
- L(2,1)-Labeling of Unigraphs (Extended Abstract)
- Introduction
- Preliminaries
- An Algorithm for L(2,1)-Labeling Unigraphs
- Labeling of the Crown and of the Pieces
- References
- Energy-Efficient Due Date Scheduling
- Introduction
- Minimizing (Weighted) Quoted Lead Time Plus Energy
- Uniform Weight Density
- Arbitrary Weight Density
- Setting with Admission Control
- References
- Go with the Flow: The Direction-Based Fr\'{e}chet Distance of Polygonal Curves
- Introduction
- Preliminaries
- Computing Fdirint(A,B)
- Exact Algorithm without Speed Limits
- (1+)-Approximation Algorithm with Speed Limits
- Conclusion
- References
- A Comparison of Three Algorithms for Approximating the Distance Distribution in Real-World Graphs
- Introduction
- Algorithms for Estimating the Distance Distribution
- The EW Algorithm
- The SEF Algorithm
- The ANF Algorithm
- Experimental Study
- Datasets
- Algorithms' Implementation and Computing Platform
- Methodology and Error Estimation
- EW versus ANF
- EW versus SEF
- EW versus the Exact Distribution
- Conclusions
- References
- Exploiting Bounded Signal Flow for Graph Orientation Based on Cause-Effect Pairs
- Introduction
- Preliminaries, Basic Facts, and Simple Observations
- Bounded Signal Flow over Vertices
- Parameter ``Maximum Number of Pairs per Vertex''
- Cross Pairs
- Cross-Pair-Free Instances
- Parameter ``Maximum Number of Cross Pairs Passing through a Vertex''
- Bounded Signal Flow over Edges
- Observations on Protein Networks
- Conclusion
- References
- On Greedy and Submodular Matrices
- Introduction
- Our Contribution and Related Results
- (Weighted) Max Flow
- Binary Greedy Matrices
- Submodular Matrices
- Example: Max Flow in (s,t)-Planar Graphs
- Example: Frank's Model frank99
- Ternary Matrices
- Example: Edge-Path Incidence Matrices in General Graphs
- Example: Lattice Polyhedra GH82
- Ordered Compatibility and Greediness
- References
- MIP Formulations for Flowshop Scheduling with Limited Buffers
- Introduction
- Previous Work
- Our Results
- Suboptimality of Permutation Schedules
- The Model
- Model Refinements and Solution Strategies
- Suitable Choice of Big-M Values
- Numerical Results
- Conclusions
- References
- A Scenario-Based Approach for Robust Linear Optimization
- Introduction
- Review of Robustness Concepts
- A Scenario-Based Approach to Robust Linear Optimization
- Analysis of Solutions Generated with RecOpt
- Evaluation of RecOpt Using Examples from NetLib
- Conclusion
- References
- Conflict Propagation and Component Recursion for Canonical Labeling
- Introduction
- Preliminaries
- Colored Graphs, Equitable Colorings, Refinement Functions
- Individualize and Refine Depth-First Search
- Pruning with Recorded First-Path Failures
- Pruning with Nonuniform Component Recursion
- Experimental Evaluation of the Pruning Techniques
- References
- 3-hitting set on Bounded Degree Hypergraphs: Upper and Lower Bounds on the Kernel Size
- Introduction
- Preliminaries
- The Lower Bound
- TheKernel
- Generalization to Bounded Degree $?$
- Concluding Remarks
- References
- Improved Taxation Rate for Bin Packing Games
- Introduction
- Fractional Packings
- Alternative Proof of the Non-emptiness of 1/3-Core
- Modified Greedy Selection
- Remarks and Open Problems
- References
- Multi-channel Assignment for Communication in Radio Networks
- Introduction
- Technical Preliminaries
- Optimal Channel Assignment
- Connectivity Problem
- One-Receiver Problem
- Gossiping
- Conclusions
- References
- Computing Strongly Connected Components in the Streaming Model
- Introduction
- Streaming Models and Graph Problems
- The Algorithm
- Theoretical Analysis
- Correctness
- Number of Streaming Passes
- Per Item Processing Time (PIPT)
- Experimental Evaluation
- Conclusion
- References
- Improved Approximation Algorithms for the Max-Edge Coloring Problem
- Introduction
- A PTAS for Trees
- Beating the 2-approximation Ratio for Bipartite Graphs
- An Adaptation for General Graphs
- Conclusions
- References
- New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches
- Introduction
- Previous Work
- New Results
- Algorithms of the List Class
- Algorithms with Approximate Priority Queues
- Experiments
- List Class Algorithms
- Algorithms with Approximate Priority Queues
- Conclusions
- References
- An Approximative Criterion for the Potential of Energetic Reasoning
- Introduction
- Problem Description and Energetic Reasoning
- Restricted Energetic Reasoning
- Estimation of Relevant Intervals
- Restricted Energetic Reasoning Propagation Algorithm
- Computational Results
- Conclusions
- References
- Speed Scaling for Energy and Performance with Instantaneous Parallelism
- Introduction
- Models and Objective Functions
- Total Flow Time Plus Energy
- Preliminaries
- U-CEQ and Performance
- Makespan Plus Energy
- Performance of the Optimal
- P-FIRST and Performance
- Discussion
- References
- Algorithms for Scheduling with Power Control in Wireless Networks
- Introduction
- Preliminaries
- The Counterexample
- Scheduling q-independent Sets
- Splitting L into a Small Number of q-independent Subsets
- Introducing the Noise Factor
- Conclusion
- References
- Author Index
