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

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 -