Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers

  • Conference proceedings
  • © 2018

Overview

Editors:
  1. Leah Epstein

    1. University of Haifa, Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Thomas Erlebach

    1. University of Leicester, Leicester, UK

    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 11312)

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

Included in the following conference series:

Conference proceedings info: WAOA 2018.

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 EPUB and 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 (20 papers)

  1. Front Matter

    Pages I-X
    Download chapter PDF

  2. Invited Contribution

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Some Easy and Some Not so Easy Geometric Optimization Problems

      • Gerhard J. Woeginger
      Pages 3-18

  3. Regular Papers

    1. Front Matter

      Pages 19-19
      Download chapter PDF

    2. Deterministic Min-Cost Matching with Delays

      • Yossi Azar, Amit Jacob Fanani
      Pages 21-35

    3. Sequential Metric Dimension

      • Julien Bensmail, Dorian Mazauric, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes
      Pages 36-50

    4. A Primal-Dual Online Deterministic Algorithm for Matching with Delays

      • Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu, PaweÅ‚ Schmidt
      Pages 51-68

    5. Advice Complexity of Priority Algorithms

      • Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
      Pages 69-86

    6. Approximating Node-Weighted k-MST on Planar Graphs

      • JarosÅ‚aw Byrka, Mateusz Lewandowski, Joachim Spoerhase
      Pages 87-101

    7. Exploring Sparse Graphs with Advice (Extended Abstract)

      • Hans-Joachim Böckenhauer, Janosch Fuchs, Walter Unger
      Pages 102-117

    8. Call Admission Problems on Grids with Advice (Extended Abstract)

      • Hans-Joachim Böckenhauer, Dennis Komm, Raphael Wegner
      Pages 118-133

    9. Improved Approximation Algorithms for Minimum Power Covering Problems

      • Gruia Calinescu, Guy Kortsarz, Zeev Nutov
      Pages 134-148

    10. DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals

      • Minjun Chang, Dorit S. Hochbaum, Quico Spaen, Mark Velednitsky
      Pages 149-164

    11. Strategic Contention Resolution in Multiple Channels

      • George Christodoulou, Themistoklis Melissourgos, Paul G. Spirakis
      Pages 165-180

    12. Sublinear Graph Augmentation for Fast Query Implementation

      • Artur Czumaj, Yishay Mansour, Shai Vardi
      Pages 181-203

    13. Bin Packing Games with Weight Decision: How to Get a Small Value for the Price of Anarchy

      • Gyorgy Dosa, Hans Kellerer, Zsolt Tuza
      Pages 204-217

    14. Probabilistic Embeddings of the Fréchet Distance

      • Anne Driemel, Amer KrivoÅ¡ija
      Pages 218-237

    15. Algorithms for Dynamic NFV Workload

      • Yaron Fairstein, Seffi (Joseph) Naor, Danny Raz
      Pages 238-258

    16. Longest Increasing Subsequence Under Persistent Comparison Errors

      • Barbara Geissmann
      Pages 259-276

    17. Cut Sparsifiers for Balanced Digraphs

      • Motoki Ikeda, Shin-ichi Tanigawa
      Pages 277-294
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

About this book

This book constitutes the thoroughly refereed workshop post-proceedings of the 16th International Workshop on Approximation and Online Algorithms, WAOA 2018, held in Helsinki, Finland, in August 2018 as part of ALGO 2018.
The 19 revised full papers presented together with one invited paper in this book were carefully reviewed and selected from 44 submissions. Topics of interest for WAOA 2016 were: graph algorithms; inapproximability results; network design; packing and covering; paradigms for the design and analysis of approximation and online algorithms; parameterized complexity; scheduling problems; algorithmic game theory; algorithmic trading; coloring and partitioning; competitive analysis; computational advertising; computational finance; cuts and connectivity; geometric problems; mechanism design; resource augmentation; and real-world applications.

Editors and Affiliations

  • University of Haifa, Haifa, Israel

    Leah Epstein

  • University of Leicester, Leicester, UK

    Thomas Erlebach

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation