Approximation and Online Algorithms

Approximation and Online Algorithms

---

10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers
Thomas Erlebach, Giuseppe Persiano (Eds.)

Table of Contents
The Primal-Dual Approach for Online Algorithms - Bansal, Nikhil - Seite 1
Independent Set with Advice: The Impact of Graph Knowledge - Dobrev, Stefan (et al.) - Seiten 2-15
Online Multi-Commodity Flow with High Demands - Even, Guy (et al.) - Seiten 16-29
Approximating Spanning Trees with Few Branches - Chimani, Markus (et al.) - Seiten 30-41
On the Complexity of the Regenerator Location Problem - Treewidth and Other Parameters - Hartstein, Itamar (et al.) - Seiten 42-55
Online Exploration of Polygons with Holes - Georges, Robert (et al.) - Seiten 56-69
Probabilistic k-Median Clustering in Data Streams - Lammersen, Christiane (et al.) - Seiten 70-81
Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs - Fonseca, Guilherme D. (et al.) - Seiten 82-92
On Minimum-and Maximum-Weight Minimum Spanning Trees with Neighborhoods - Dorrigiv, Reza (et al.) - Seiten 93-106
Asymptotically Optimal Online Page Migration on Three Points - Matsubayashi, Akira - Seiten 107-119
R–LINE: A Better Randomized 2-Server Algorithm on the Line - Bang, Lucas (et al.) - Seiten 120-130
Black and White Bin Packing - Balogh, János (et al.) - Seiten 131-144
Minimizing Cache Usage in Paging - López-Ortiz, Alejandro (et al.) - Seiten 145-158
Competitive-Ratio Approximation Schemes for Makespan Scheduling Problems - Kurpisz, Adam (et al.) - Seiten 159-172
Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling - Gupta, Anupam (et al.) - Seiten 173-186
Approximating the Throughput by Coolest First Scheduling - Dürr, Christoph (et al.) - Seiten 187-200
Algorithms for Cost-Aware Scheduling - Kulkarni, Janardhan (et al.) - Seiten 201-214
A Unifying Tool for Bounding the Quality of Non-cooperative Solutions in Weighted Congestion Games - Bilò, Vittorio - Seiten 215-228
Some Anomalies of Farsighted Strategic Behavior - Bilò, Vittorio (et al.) - Seiten 229-241
Scheduling with an Orthogonal Resource Constraint - Niemeier, Martin (et al.) - Seiten 242-256
Improved Approximation Guarantees for Lower-Bounded Facility Location - Ahmadian, Sara (et al.) - Seiten 257-271
A 4-Approximation for the Height of Drawing 2-Connected Outer-Planar Graphs - Biedl, Therese - Seiten 272-285
Approximation Algorithms for the Wafer to Wafer Integration Problem - Dokka, Trivikram (et al.) - Seiten 286-297

---

Springer, Paperback, Notes in Computer Science - Volume 7846, english, 312 pages, still sealed