Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009 Revised Papers

  • Conference proceedings
  • © 2010

Overview

Editors:
  1. Evripidis Bampis

    1. IBISC, CNRS FRE 3190, Université d’Evry Val d’Essonne, Evry Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institute for Computer Science and Applied Mathematics, University of Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Up-to-date results
  • Fast track conference proceeding
  • State-of-the-art report

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

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

Included in the following conference series:

Conference proceedings info: WAOA 2009.

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 (22 papers)

  1. Front Matter

    Download chapter PDF

  2. WAOA 2009

    1. On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems

      • Spyros Angelopoulos
      Pages 1-12

    2. Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications

      • Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz
      Pages 13-24

    3. Price Fluctuations: To Buy or to Rent

      • Marcin Bienkowski
      Pages 25-36

    4. Approximation Algorithms for Multiple Strip Packing

      • Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Otte, Denis Trystram
      Pages 37-48

    5. Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window

      • Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting
      Pages 49-61

    6. Longest Wait First for Broadcast Scheduling [Extended Abstract]

      • Chandra Chekuri, Sungjin Im, Benjamin Moseley
      Pages 62-74

    7. The Routing Open Shop Problem: New Approximation Algorithms

      • Ilya Chernykh, Nikita Dryuck, Alexander Kononov, Sergey Sevastyanov
      Pages 75-85

    8. On the Price of Stability for Undirected Network Design

      • George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, Rob van Stee
      Pages 86-97

    9. Finding Dense Subgraphs in G(n,1/2)

      • Atish Das Sarma, Amit Deshpande, Ravi Kannan
      Pages 98-103

    10. Parameterized Analysis of Paging and List Update Algorithms

      • Reza Dorrigiv, Martin R. Ehmsen, Alejandro López-Ortiz
      Pages 104-115

    11. Online Scheduling of Bounded Length Jobs to Maximize Throughput

      • Christoph Dürr, Łukasz Jeż, Kim Thang Nguyen
      Pages 116-127

    12. On the Additive Constant of the k-Server Work Function Algorithm

      • Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosén
      Pages 128-134

    13. A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

      • Thomas Erlebach, Matúš Mihalák
      Pages 135-146

    14. Guard Games on Graphs: Keep the Intruder Out!

      • Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov
      Pages 147-158

    15. Between a Rock and a Hard Place: The Two-to-One Assignment Problem

      • Dries Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger
      Pages 159-169

    16. Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width

      • Elisabeth Günther, Felix G. König, Nicole Megow
      Pages 170-181

    17. Online Minimization Knapsack Problem

      • Xin Han, Kazuhisa Makino
      Pages 182-193

    18. Optimization Problems in Multiple Subtree Graphs

      • Danny Hermelin, Dror Rawitz
      Pages 194-204

    19. Multi-Criteria TSP: Min and Max Combined

      • Bodo Manthey
      Pages 205-216
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

Editors and Affiliations

  • IBISC, CNRS FRE 3190, Université d’Evry Val d’Essonne, Evry Cedex, France

    Evripidis Bampis

  • Institute for Computer Science and Applied Mathematics, University of Kiel, Kiel, Germany

    Klaus Jansen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation