Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers

  • Conference proceedings
  • © 2013

Overview

Editors:
  1. Thomas Erlebach

    1. Department of Computer Science, University of Leicester, Leicester, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Giuseppe Persiano

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Fast-track conference proceedings
  • State-of-the-art research
  • Up-to-date results

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 7846)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: WAOA 2012.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (23 papers)

  1. Front Matter

    Download chapter 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
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

About this book

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.

Editors and Affiliations

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

    Thomas Erlebach

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

    Giuseppe Persiano

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation