Approximation and Online Algorithms: 7th International Workshop,WAOA 2009, Copenhagen Denmark, September 10-11, 2009. Revised Papers

✍ Scribed by Spyros Angelopoulos (auth.), Evripidis Bampis, Klaus Jansen (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2010
• Tongue: English
• Leaves: 264
• Series: Lecture Notes in Computer Science 5893 : Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post workshop proceedings of the 7th International Workshop on Approximation and Online Algorithms, WAOA 2009, held in Copenhagen, Denmark, in September 2009 as part of the ALGO 2009 conference event. The 22 revised full papers presented were carefully reviewed and selected from 62 submissions. The workshop covered areas such as algorithmic game theory, approximation classes, coloring and partitioning, competitive analysis, computational finance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, parameterized complexity, randomization techniques, real-world applications, and scheduling problems.

✦ Table of Contents

Front Matter....Pages -
On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems....Pages 1-12
Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications....Pages 13-24
Price Fluctuations: To Buy or to Rent....Pages 25-36
Approximation Algorithms for Multiple Strip Packing....Pages 37-48
Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window....Pages 49-61
Longest Wait First for Broadcast Scheduling [Extended Abstract]....Pages 62-74
The Routing Open Shop Problem: New Approximation Algorithms....Pages 75-85
On the Price of Stability for Undirected Network Design....Pages 86-97
Finding Dense Subgraphs in G ( n ,1/2)....Pages 98-103
Parameterized Analysis of Paging and List Update Algorithms....Pages 104-115
Online Scheduling of Bounded Length Jobs to Maximize Throughput....Pages 116-127
On the Additive Constant of the k -Server Work Function Algorithm....Pages 128-134
A (4 +  ε )-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs....Pages 135-146
Guard Games on Graphs: Keep the Intruder Out!....Pages 147-158
Between a Rock and a Hard Place: The Two-to-One Assignment Problem....Pages 159-169
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width....Pages 170-181
Online Minimization Knapsack Problem....Pages 182-193
Optimization Problems in Multiple Subtree Graphs....Pages 194-204
Multi-Criteria TSP: Min and Max Combined....Pages 205-216
Packet Routing: Complexity and Algorithms....Pages 217-228
Minimal Cost Reconfiguration of Data Placement in Storage Area Network....Pages 229-241
Competitive Multi-dimensional Dynamic Bin Packing via L-Shape Bin Packing....Pages 242-254
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Graphics; Data Structures; Algorithms