Theory and Practice of Algorithms in (Computer) Systems : First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, Proceedings

by Marchetti-Spaccamela, Alberto; Segal, Michae

• ISBN13: 9783642197536
• ISBN10: 3642197531
• Format: Paperback
• Copyright: 2011-05-03
• Publisher: Springer-Verlag New York Inc

Summary

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.

Table of Contents

Distributed Decision Problems: The Locality Angle (Invited Talk)	p. 1
Managing Power Heterogeneity (Invited Talk)	p. 6
The Mathematics of Mobility (Invited Talk)	p. 8
Speed Scaling to Manage Temperature	p. 9
Alternative Route Graphs in Road Networks	p. 21
Robust Line Planning in Case of Multiple Pools and Disruptions	p. 33
Exact Algorithms for Intervalizing Colored Graphs	p. 45
L(2,1)-Labeling of Unigraphs (Extended Abstract)	p. 57
Energy-Efficient Due Date Scheduling	p. 69
Go with the Flow: The Direction-Based Fréchet Distance of Polygonal Curves	p. 81
A Comparison of Three Algorithms for Approximating the Distance Distribution in Real-World Graphs	p. 92
Exploiting Bounded Signal Flow for Graph Orientation Based on Cause-Effect Pairs	p. 104
On Greedy and Submodular Matrices	p. 116
MIP Formulations for Flowshop Scheduling with Limited Buffers	p. 127
A Scenario-Based Approach for Robust Linear Optimization	p. 139
Conflict Propagation and Component Recursion for Canonical Labeling	p. 151
3-Hittting Set on Bounded Degree Hypergraphs: Upper and Lower Bounds on the Kernel Size	p. 163
Improved Taxation Rate for Bin Packing Games	p. 175
Multi-channel Assignment for Communication in Radio Networks	p. 181
Computing Strongly Connected Components in the Streaming Model	p. 193
Improved Approximation Algorithms for the Max-Edge Coloring Problem	p. 206
New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches	p. 217
An Approximative Criterion for the Potential of Energetic Reasoning	p. 229
Speed Scaling for·Energy and Performance with Instantaneous Parallelism	p. 240
Algorithms for Scheduling with Power Control in Wireless Networks	p. 252
Author Index	p. 265
Table of Contents provided by Ingram. All Rights Reserved.