## Theory and Practice of Algorithms in (Computer) Systems: First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, ProceedingsAlberto Marchetti-Spaccamela, Michael Segal 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

The Locality Angle | 1 |

Managing Power Heterogeneity | 6 |

The Mathematics of Mobility | 8 |

Speed Scaling to Manage Temperature | 9 |

Alternative Route Graphs in Road Networks | 21 |

Robust Line Planning in Case of Multiple Pools and Disruptions | 33 |

Exact Algorithms for Intervalizing Colored Graphs | 45 |

L21Labeling of Unigraphs Extended Abstract | 57 |

A ScenarioBased Approach for Robust Linear Optimization | 139 |

Conflict Propagation and Component Recursion for Canonical Labeling | 151 |

Upper and Lower Bounds on the Kernel Size | 163 |

Improved Taxation Rate for Bin Packing Games | 175 |

Multichannel Assignment for Communication in Radio Networks | 181 |

Computing Strongly Connected Components in the Streaming Model | 193 |

Improved Approximation Algorithms for the MaxEdge Coloring Problem | 206 |

On the AverageCase Behavior of Classic SingleSource ShortestPaths Approaches | 217 |

EnergyEfficient Due Date Scheduling | 69 |

The DirectionBased Frechet Distance of Polygonal Curves | 81 |

A Comparison of Three Algorithms for Approximating the Distance Distribution in RealWorld Graphs | 92 |

Exploiting Bounded Signal Flow for Graph Orientation Based on CauseEffect Pairs | 104 |

On Greedy and Submodular Matrices | 116 |

MIP Formulations for Flowshop Scheduling with Limited Buffers | 127 |

An Approximative Criterion for the Potential of Energetic Reasoning | 229 |

Speed Scaling for Energy and Performance with Instantaneous Parallelism | 240 |

Algorithms for Scheduling with Power Control in Wireless Networks | 252 |

264 | |

### Other editions - View all

### Common terms and phrases

approximation assume Berlin Heidelberg 2011 bipartite graphs canonical labeling cell channels colored graph competitive ratio completion compute consider constraint curves defined degree-2 denote directed graph direction-based edge weights energetic reasoning feasible fixed-parameter tractable Fréchet distance function graph G greedy algorithm grid graphs Heidelberg hence hitting set hypergraphs input instance interval interval graph isomorphic kernel kSEF Lemma LNCS logn LOPs lower bound makespan makespan plus energy Marchetti-Spaccamela matrices maximum MaxW MEC problem minimizing node nonuniform components NP-complete NP-hard online algorithm optimal solution parameter partial path decomposition permutation polygonal curves polynomial pool processor Proof properly colored ratio RecOpt refinement function robust solution routes running scenarios schedule set nodes shortest path solved speed scaling Springer subgraph submodular subset temperature Theorem tree UMaxW upper bound variables vector vertices weighted flow