Skip to main content
SpringerLink
Log in

Approximation and Online Algorithms

19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021, Revised Selected Papers

  • Conference proceedings
  • © 2021

Overview

Editors:
  1. Jochen Koenemann

    1. University of Waterloo, Waterloo, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Britta Peis

    1. RWTH Aachen University, Aachen, 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 12982)

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

Included in the following conference series:

Conference proceedings info: WAOA 2021.

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 49.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 64.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

About this book

This book constitutes the thoroughly refereed workshop post-proceedings of the 19th International Workshop on Approximation and Online Algorithms, WAOA 2021, held in September 2021. Due to COVID-19 pandemic the conference was held virtually.

The 16 revised full papers presented in this book were carefully reviewed and selected from 31 submissions. The papers focus on the design and analysis of algorithms for online and computationally hard problems.

Similar content being viewed by others

Keywords

Table of contents (16 papers)

  1. Front Matter

    Pages i-xii
    Download chapter PDF

  2. Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle

    • Waldo Gálvez, Francisco Sanhueza-Matamala, José A. Soto
    Pages 1-22

  3. Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set

    • Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišt’an, Ondřej Suchý, Tomáš Valla
    Pages 23-38Open Access

  4. An Improved Approximation Bound for Minimum Weight Dominating Set on Graphs of Bounded Arboricity

    • Hao Sun
    Pages 39-47

  5. Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems

    • Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski
    Pages 48-64

  6. On b-Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 4-Edge Dominating Set Problem

    • Toshihiro Fujito, Takumi Tatematsu
    Pages 65-79

  7. The Traveling k-Median Problem: Approximating Optimal Network Coverage

    • Dylan Huizing, Guido Schäfer
    Pages 80-98

  8. EPTAS for Load Balancing Problem on Parallel Machines with a Non-renewable Resource

    • G. Jaykrishnan, Asaf Levin
    Pages 99-116

  9. Several Methods of Analysis for Cardinality Constrained Bin Packing

    • Leah Epstein
    Pages 117-129

  10. Weighted Completion Time Minimization for Capacitated Parallel Machines

    • Ilan Reuven Cohen, Izack Cohen, Iyar Zaks
    Pages 130-143

  11. Server Cloud Scheduling

    • Marten Maack, Friedhelm Meyer auf der Heide, Simon Pukrop
    Pages 144-164

  12. FIFO and Randomized Competitive Packet Routing Games

    • Bjoern Tauer, Laura Vargas Koch
    Pages 165-187

  13. Improved Online Algorithm for Fractional Knapsack in the Random Order Model

    • Jeff Giliberti, Andreas Karrenbauer
    Pages 188-205

  14. Fractionally Subadditive Maximization Under an Incremental Knapsack Constraint

    • Yann Disser, Max Klimm, David Weckbecker
    Pages 206-223

  15. Improved Analysis of Online Balanced Clustering

    • Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jiří Sgall, Pavel Veselý
    Pages 224-233

  16. Precedence-Constrained Covering Problems with Multiplicity Constraints

    • Stavros G. Kolliopoulos, Antonis Skarlatos
    Pages 234-251

  17. Contention Resolution, Matrix Scaling and Fair Allocation

    • Nikhil Bansal, Ilan Reuven Cohen
    Pages 252-274

  18. Back Matter

    Pages 275-275
    Download chapter PDF
Back to top

Other volumes

  1. Approximation and Online Algorithms

Editors and Affiliations

  • University of Waterloo, Waterloo, Canada

    Jochen Koenemann

  • RWTH Aachen University, Aachen, Germany

    Britta Peis

Bibliographic Information

  • Book Title: Approximation and Online Algorithms

  • Book Subtitle: 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021, Revised Selected Papers

  • Editors: Jochen Koenemann, Britta Peis

  • Series Title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/978-3-030-92702-8

  • Publisher: Springer Cham

  • eBook Packages: Computer Science, Computer Science (R0)

  • Copyright Information: Springer Nature Switzerland AG 2021

  • Softcover ISBN: 978-3-030-92701-1Published: 23 December 2021

  • eBook ISBN: 978-3-030-92702-8Published: 01 January 2022

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition Number: 1

  • Number of Pages: XII, 275

  • Number of Illustrations: 12 b/w illustrations, 12 illustrations in colour

  • Topics: Computational Mathematics and Numerical Analysis

Publish with us

Policies and ethics

Back to top

Search

Navigation