
Theory and Practice of Algorithms in (Computer) Systems
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

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
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.