Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. 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

  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

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

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

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

Included in the following conference series:

Conference proceedings info: WAOA 2011.

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 54.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 69.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. Approximation Algorithms for Scheduling and Packing Problems

    • Klaus Jansen
    Pages 1-8

  3. Approximating Subset k-Connectivity Problems

    • Zeev Nutov
    Pages 9-20

  4. Learning in Stochastic Machine Scheduling

    • Sebastián Marbán, Cyriel Rutten, Tjark Vredeveld
    Pages 21-34

  5. An Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems

    • Wolfgang Bein, Naoki Hatta, Nelson Hernandez-Cons, Hiro Ito, Shoji Kasahara, Jun Kawahara
    Pages 35-48

  6. Single Approximation for Biobjective Max TSP

    • Cristina Bazgan, Laurent Gourvès, Jérôme Monnot, Fanny Pascual
    Pages 49-62

  7. Parameterized Approximation Algorithms for Hitting Set

    • Ljiljana Brankovic, Henning Fernau
    Pages 63-76

  8. Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs

    • Nadine Schwartges, Joachim Spoerhase, Alexander Wolff
    Pages 77-88

  9. Optimization over Integers with Robustness in Cost and Few Constraints

    • Kai-Simon Goetzmann, Sebastian Stiller, Claudio Telha
    Pages 89-101

  10. A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption

    • Tomáš Ebenlendr, Jiří Sgall
    Pages 102-108

  11. Scheduling Jobs on Identical and Uniform Processors Revisited

    • Klaus Jansen, Christina Robenek
    Pages 109-122

  12. Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat

    • David B. Shmoys, Gwen Spencer
    Pages 123-136

  13. Non-clairvoyant Weighted Flow Time Scheduling on Different Multi-processor Models

    • Jianqiao Zhu, Ho-Leung Chan, Tak-Wah Lam
    Pages 137-149

  14. A New Perspective on List Update: Probabilistic Locality and Working Set

    • Reza Dorrigiv, Alejandro López-Ortiz
    Pages 150-163

  15. OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

    • Gerth Stølting Brodal, Gabriel Moruz, Andrei Negoescu
    Pages 164-175

  16. Faster and Simpler Approximation of Stable Matchings

    • Katarzyna Paluch
    Pages 176-187

  17. Simpler 3/4-Approximation Algorithms for MAX SAT

    • Anke van Zuylen
    Pages 188-197

  18. On Online Algorithms with Advice for the k-Server Problem

    • Marc P. Renault, Adi Rosén
    Pages 198-210

  19. Improved Lower Bound for Online Strip Packing

    • Rolf Harren, Walter Kern
    Pages 211-218

  20. Competitive Router Scheduling with Structured Data

    • Yishay Mansour, Boaz Patt-Shamir, Dror Rawitz
    Pages 219-232
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

About this book

This book constitutes the thoroughly refereed post-proceedings of the 9th International Workshop on Approximation and Online Algorithms, WAOA 2011, held in Saarbrücken, Germany, in September 2011. The 21 papers presented were carefully reviewed and selected from 48 submissions. The volume also contains an extended abstract of the invited talk of Prof. Klaus Jansen. The Workshop on Approximation and Online Algorithms focuses on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applications in a wide variety of fields. Topics of interest for WAOA 2011 were: 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, parameterized complexity, randomization techniques and scheduling problems.

Editors and Affiliations

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

    Roberto Solis-Oba

  • 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