Skip to main content
SpringerLink
Log in

Approximation and Online Algorithms

6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008, Revised Papers

  • Conference proceedings
  • © 2009

Overview

Editors:
  1. Evripidis Bampis

    1. IBISC, CNRS FRE 3190, Université d’Evry Val d’Essonne, Boulevard François Mitterand,, Evry Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Martin Skutella

    1. Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften, Berlin, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

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

Included in the following conference series:

Conference proceedings info: WAOA 2008.

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 2008

    1. Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees

      • Jochen Könemann, Ojas Parekh, David Pritchard
      Pages 1-14

    2. Size Versus Stability in the Marriage Problem

      • Péter Biró, David F. Manlove, Shubham Mittal
      Pages 15-28

    3. Degree-Constrained Subgraph Problems: Hardness and Approximation Results

      • Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh
      Pages 29-42

    4. A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines

      • Tomáš Ebenlendr, Jiří Sgall
      Pages 43-52

    5. Improved Randomized Online Scheduling of Unit Length Intervals and Jobs

      • Stanley P. Y. Fung, Chung Keung Poon, Feifeng Zheng
      Pages 53-66

    6. Minimizing Average Flow Time on Unrelated Machines

      • René A. Sitters
      Pages 67-77

    7. Cooperation in Multiorganization Matching

      • Laurent Gourvès, Jérôme Monnot, Fanny Pascual
      Pages 78-91

    8. Randomized Algorithms for Buffer Management with 2-Bounded Delay

      • Marcin Bienkowski, Marek Chrobak, Łukasz Jeż
      Pages 92-104

    9. A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints

      • Clemens Thielen, Sven O. Krumke
      Pages 105-118

    10. Malicious Bayesian Congestion Games

      • Martin Gairing
      Pages 119-132

    11. Stackelberg Strategies and Collusion in Network Games with Splittable Flow

      • Tobias Harks
      Pages 133-146

    12. Peak Shaving through Resource Buffering

      • Amotz Bar-Noy, Matthew P. Johnson, Ou Liu
      Pages 147-159

    13. On Lagrangian Relaxation and Subset Selection Problems

      • Ariel Kulik, Hadas Shachnai
      Pages 160-173

    14. Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements

      • Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson
      Pages 174-187

    15. Caching Content under Digital Rights Management

      • Leah Epstein, Amos Fiat, Meital Levy
      Pages 188-200

    16. Reoptimization of Weighted Graph and Covering Problems

      • Davide Bilò, Peter Widmayer, Anna Zych
      Pages 201-213

    17. Smoothing Imprecise 1.5D Terrains

      • Chris Gray, Maarten Löffler, Rodrigo I. Silveira
      Pages 214-226

    18. Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs

      • Andreas Wiese, Evangelos Kranakis
      Pages 227-240

    19. Dynamic Offline Conflict-Free Coloring for Unit Disks

      • Joseph Wun-Tat Chan, Francis Y. L. Chin, Xiangyu Hong, Hing Fung Ting
      Pages 241-252
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 6th International Workshop on Approximation and Online Algorithms, WAOA 2008, held in Karlsruhe, Germany, in September 2008 as part of the ALGO 2008 conference event. The 22 revised full papers presented were carefully reviewed and selected from 56 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, mechanism design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, randomization techniques, real-world applications, and scheduling problems.

Editors and Affiliations

  • IBISC, CNRS FRE 3190, Université d’Evry Val d’Essonne, Boulevard François Mitterand,, Evry Cedex, France

    Evripidis Bampis

  • Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften, Berlin, Germany

    Martin Skutella

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation