Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

8th International Workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010, Revised Papers

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Klaus Jansen

    1. Department of Computer Science, University of Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Roberto Solis-Oba

    1. Department of Computer Science, The University of Western Ontario, London, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • High quality selected papers
  • Unique visibility
  • State of the art research

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

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

Included in the following conference series:

Conference proceedings info: WAOA 2010.

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. WAOA 2010

    1. Strategic Multiway Cut and Multicut Games

      • Elliot Anshelevich, Bugra Caskurlu, Ameya Hate
      Pages 1-12

    2. Approximating Directed Buy-at-Bulk Network Design

      • Spyridon Antonakopoulos
      Pages 13-24

    3. New Lower Bounds for Certain Classes of Bin Packing Algorithms

      • János Balogh, József Békési, Gábor Galambos
      Pages 25-36

    4. On the Approximation Complexity Hierarchy

      • Magnus Bordewich
      Pages 37-46

    5. The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers

      • Patrick Briest, Heiko Röglin
      Pages 47-58

    6. Tradeoff between Energy and Throughput for Online Deadline Scheduling

      • Ho-Leung Chan, Tak-Wah Lam, Rongbin Li
      Pages 59-70

    7. New Models and Algorithms for Throughput Maximization in Broadcast Scheduling

      • Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen et al.
      Pages 71-82

    8. Densest k-Subgraph Approximation on Intersection Graphs

      • Danny Z. Chen, Rudolf Fleischer, Jian Li
      Pages 83-93

    9. The Train Delivery Problem - Vehicle Routing Meets Bin Packing

      • Aparna Das, Claire Mathieu, Shay Mozes
      Pages 94-105

    10. An FPTAS for Flows over Time with Aggregate Arc Capacities

      • Daniel Dressler, Martin Skutella
      Pages 106-117

    11. List Factoring and Relative Worst Order Analysis

      • Martin R. Ehmsen, Jens S. Kohrt, Kim S. Larsen
      Pages 118-129

    12. Approximation Algorithms for Domination Search

      • Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos
      Pages 130-141

    13. Lower Bounds for Smith’s Rule in Stochastic Machine Scheduling

      • Caroline Jagtenberg, Uwe Schwiegelshohn, Marc Uetz
      Pages 142-153

    14. Approximating Survivable Networks with Minimum Number of Steiner Points

      • Lior Kamma, Zeev Nutov
      Pages 154-165

    15. A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

      • Andreas Karrenbauer, Thomas Rothvoß
      Pages 166-177

    16. Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data

      • Tak-Wah Lam, Chi-Man Liu, Hing-Fung Ting
      Pages 178-189

    17. How to Play Unique Games on Expanders

      • Konstantin Makarychev, Yury Makarychev
      Pages 190-200

    18. Online Ranking for Tournament Graphs

      • Claire Mathieu, Adrian Vladu
      Pages 201-212

    19. Throughput Maximization for Periodic Packet Routing on Trees and Grids

      • Britta Peis, Andreas Wiese
      Pages 213-224
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 8th International Workshop on Approximation and Online Algorithms, WAOA 2010, held in Liverpool, UK, in September 2010 as part of the ALGO 2010 conference event.

The 23 revised full papers presented were carefully reviewed and
selected from 58 submissions. The workshop covered areas such as
algorithmic game theory, approximation classes, coloring and
partitioning, competitive analysis, computational finance, cuts and
connectivity, geometric problems, inapproximability results, echanism
design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, parameterized
complexity, randomization techniques, real-world applications, and
scheduling problems.

Editors and Affiliations

  • Department of Computer Science, University of Kiel, Kiel, Germany

    Klaus Jansen

  • Department of Computer Science, The University of Western Ontario, London, Canada

    Roberto Solis-Oba

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation