Approximation and Online Algorithms: 10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers

✍ Scribed by Nikhil Bansal (auth.), Thomas Erlebach, Giuseppe Persiano (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2013
• Tongue: English
• Leaves: 308
• Series: Lecture Notes in Computer Science 7846
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post workshop proceedings of the 10th International Workshop on Approximation and Online Algorithms, WAOA 2012, held in Ljubljana, Slovenia, in September 2012 as part of the ALGO 2012 conference event. The 22 revised full papers presented together with invited talk were carefully reviewed and selected from 60 submissions. The workshop covered areas such as geometric problems, online algorithms, scheduling, algorithmic game theory, and approximation algorithms.

✦ Table of Contents

Front Matter....Pages -
The Primal-Dual Approach for Online Algorithms....Pages 1-1
Independent Set with Advice: The Impact of Graph Knowledge....Pages 2-15
Online Multi-Commodity Flow with High Demands....Pages 16-29
Approximating Spanning Trees with Few Branches....Pages 30-41
On the Complexity of the Regenerator Location Problem - Treewidth and Other Parameters....Pages 42-55
Online Exploration of Polygons with Holes....Pages 56-69
Probabilistic k -Median Clustering in Data Streams....Pages 70-81
Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs....Pages 82-92
On Minimum-and Maximum-Weight Minimum Spanning Trees with Neighborhoods....Pages 93-106
Asymptotically Optimal Online Page Migration on Three Points....Pages 107-119
R–LINE: A Better Randomized 2-Server Algorithm on the Line....Pages 120-130
Black and White Bin Packing....Pages 131-144
Minimizing Cache Usage in Paging....Pages 145-158
Competitive-Ratio Approximation Schemes for Makespan Scheduling Problems....Pages 159-172
Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling....Pages 173-186
Approximating the Throughput by Coolest First Scheduling....Pages 187-200
Algorithms for Cost-Aware Scheduling....Pages 201-214
A Unifying Tool for Bounding the Quality of Non-cooperative Solutions in Weighted Congestion Games....Pages 215-228
Some Anomalies of Farsighted Strategic Behavior....Pages 229-241
Scheduling with an Orthogonal Resource Constraint....Pages 242-256
Improved Approximation Guarantees for Lower-Bounded Facility Location....Pages 257-271
A 4-Approximation for the Height of Drawing 2-Connected Outer-Planar Graphs....Pages 272-285
Approximation Algorithms for the Wafer to Wafer Integration Problem....Pages 286-297
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Graphics; Information Systems Applications (incl. Internet); Algorithms