Approximation and Online Algorithms

1. Front Matter

   Pages i-xii

   PDF

2. Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains

   • Stav Ashur, Omrit Filtser, Matthew J. Katz, Rachel Saban

   Pages 1-17

3. A New Lower Bound for Classic Online Bin Packing

   • János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

   Pages 18-28

4. Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s, t)-Cuts

   • Pierre Bergé, Lou Salaün

   Pages 29-42

5. Robust Online Algorithms for Certain Dynamic Packing Problems

   • Sebastian Berndt, Valentin Dreismann, Kilian Grage, Klaus Jansen, Ingmar Knof

   Pages 43-59

6. Approximation Results for Makespan Minimization with Budgeted Uncertainty

   • Marin Bougeret, Klaus Jansen, Michael Poss, Lars Rohwedder

   Pages 60-71

7. Streaming Algorithms for Bin Packing and Vector Scheduling

   • Graham Cormode, Pavel Veselý

   Pages 72-88

8. An Improved Upper Bound for the Ring Loading Problem

   • Karl Däubel

   Pages 89-105

9. Parallel Online Algorithms for the Bin Packing Problem

   • Sándor P. Fekete, Jonas Grosse-Holz, Phillip Keldenich, Arne Schmidt

   Pages 106-119

10. Managing Multiple Mobile Resources

    • Björn Feldkord, Till Knollmann, Manuel Malatyali, Friedhelm Meyer auf der Heide

    Pages 120-137

11. On the Cycle Augmentation Problem: Hardness and Approximation Algorithms

    • Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Krzysztof Sornat

    Pages 138-153

12. Approximate Strong Edge-Colouring of Unit Disk Graphs

    • Nicolas Grelier, Rémi de Joannis de Verclos, Ross J. Kang, François Pirot

    Pages 154-169

13. Precedence-Constrained Scheduling and Min-Sum Set Cover

    • Felix Happach, Andreas S. Schulz

    Pages 170-187

14. Fault Tolerant Clustering with Outliers

    • Tanmay Inamdar, Kasturi Varadarajan

    Pages 188-201

15. Improved (In-)Approximability Bounds for d-Scattered Set

    • Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

    Pages 202-216

16. Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs

    • Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong

    Pages 217-231

17. Fair Coresets and Streaming Algorithms for Fair k-means

    • Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler

    Pages 232-251

18. Correction to: Approximation and Online Algorithms

    • Evripidis Bampis, Nicole Megow

    Pages C1-C1

19. Back Matter

    Pages 253-253

    PDF

This book constitutes the thoroughly refereed workshop post-proceedings of the 17th International Workshop on Approximation and Online Algorithms, WAOA 2019, held in Munich, Germany, in September 2019 as part of ALGO 2019.
The 16 revised full papers presented together with one invited paper in this book were carefully reviewed and selected from 38 submissions. Topics of interest for WAOA 2018 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.

• approximation algorithms
• approximation ratios
• approximation theory
• artificial intelligence
• bin packing
• combinatorial optimization
• competitive ratio
• computer networks
• computer science
• computer systems
• directed graphs
• distributed computer systems
• distributed systems
• graph theory
• mathematics
• on-line algorithms
• online systems
• optimization
• polynomial approximation
• theoretical computer science

• LIP6, Sorbonne University, Paris, France

  Evripidis Bampis

• Department for Mathematics and Computer Science, University of Bremen, Bremen, Germany

  Nicole Megow

Policies and ethics