Approximation and Online Algorithms

1. Front Matter

   PDF

2. Invited Contribution

   1. The Primal-Dual Approach for Online Algorithms

      • Nikhil Bansal

      Pages 1-1

3. Session 1: Graphs and Networks

   1. Independent Set with Advice: The Impact of Graph Knowledge

      • Stefan Dobrev, Rastislav Královič, Richard Královič

      Pages 2-15

   2. Online Multi-Commodity Flow with High Demands

      • Guy Even, Moti Medina

      Pages 16-29

   3. Approximating Spanning Trees with Few Branches

      • Markus Chimani, Joachim Spoerhase

      Pages 30-41

   4. On the Complexity of the Regenerator Location Problem - Treewidth and Other Parameters

      • Itamar Hartstein, Mordechai Shalom, Shmuel Zaks

      Pages 42-55

4. Session 2: Geometric Problems

   1. Online Exploration of Polygons with Holes

      • Robert Georges, Frank Hoffmann, Klaus Kriegel

      Pages 56-69

   2. Probabilistic k-Median Clustering in Data Streams

      • Christiane Lammersen, Melanie Schmidt, Christian Sohler

      Pages 70-81

   3. Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs

      • Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. P. de Sá, Raphael Machado

      Pages 82-92

   4. On Minimum-and Maximum-Weight Minimum Spanning Trees with Neighborhoods

      • Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz et al.

      Pages 93-106

5. Session 3: Online Algorithms

   1. Asymptotically Optimal Online Page Migration on Three Points

      • Akira Matsubayashi

      Pages 107-119

   2. R–LINE: A Better Randomized 2-Server Algorithm on the Line

      • Lucas Bang, Wolfgang Bein, Lawrence L. Larmore

      Pages 120-130

   3. Black and White Bin Packing

      • János Balogh, József Békési, Gyorgy Dosa, Hans Kellerer, Zsolt Tuza

      Pages 131-144

   4. Minimizing Cache Usage in Paging

      • Alejandro López-Ortiz, Alejandro Salinger

      Pages 145-158

6. Session 4: Scheduling

   1. Competitive-Ratio Approximation Schemes for Makespan Scheduling Problems

      • Adam Kurpisz, Monaldo Mastrolilli, Georgios Stamoulis

      Pages 159-172

   2. Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling

      • Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs

      Pages 173-186

   3. Approximating the Throughput by Coolest First Scheduling

      • Christoph Dürr, Ioannis Milis, Julien Robert, Georgios Zois

      Pages 187-200

   4. Algorithms for Cost-Aware Scheduling

      • Janardhan Kulkarni, Kamesh Munagala

      Pages 201-214

7. Session 5: Algorithmic Game Theory

   1. A Unifying Tool for Bounding the Quality of Non-cooperative Solutions in Weighted Congestion Games

      • Vittorio Bilò

      Pages 215-228

   2. Some Anomalies of Farsighted Strategic Behavior

      • Vittorio Bilò, Michele Flammini, Gianpiero Monaco, Luca Moscardelli

      Pages 229-241

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.

• approximation algorithms
• competitive analysis
• graph drawing
• online algorithms
• wafer-to-wafer integration
• algorithm analysis and problem complexity

• Department of Computer Science, University of Leicester, Leicester, UK

  Thomas Erlebach

• Dipartimento di Informatica "Renato M. Capocelli", Università di Salerno, Fisciano, Italy

  Giuseppe Persiano

Policies and ethics