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.

Includes author index.

Intro -- Preface -- Organization -- On the Hardness of Computing the Diameter of a Polytope (Invited Talk) -- Contents -- Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains -- 1 Introduction -- 2 A PTAS for Minimum Dominating Set in Terrain-Like Graphs -- 2.1 Algorithm -- 2.2 Analysis -- 2.3 Maximum Independent Set -- 3 Guarding the Vertices -- 3.1 x-monotone (1.5D) Terrains -- 3.2 WV-polygons -- 3.3 WV-terrains: Removing the Monotonicity Assumption -- 4 Guarding the Boundary -- 4.1 The Semi-continuous Version -- 4.2 The Continuous Version

5 Terrain-Like vs. Non-jumping -- References -- A New Lower Bound for Classic Online Bin Packing -- 1 Introduction -- 1.1 New Features of Our Work -- 2 The Input -- 3 Bounds on the Optimal Costs -- 4 An Analysis Using Weights -- 4.1 The Assignment of Weights to Items -- 4.2 Definition of Bin Types -- 4.3 The Price of a Bin Type -- 4.4 Calculating the Prices of the Bin Types -- 4.5 Using the Prices of Bin Types to Establish the Lower Bound on the Asymptotic Competitive Ratio -- References -- Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s, t)-Cuts

1 Introduction -- 2 Preliminaries -- 3 Competitive Ratio of Existing Strategies When max< k -- 4 Detour Strategy -- 4.1 Description of -Detour Strategy -- 4.2 Competitive Analysis -- 4.3 Discussion -- 5 Conclusion -- References -- Robust Online Algorithms for Certain Dynamic Packing Problems -- 1 Introduction -- 1.1 Related Works -- 1.2 Our Results -- 2 Online Algorithms for Dynamic Problems: A Framework -- 3 2-Dimensional Strip Packing -- 4 Bin Packing -- 5 Vector Packing -- References -- Approximation Results for Makespan Minimization with Budgeted Uncertainty -- 1 Introduction

2 A 3-Approximation for Unrelated Machines -- 3 A 2- Inapproximability for Unrelated Machines -- 4 A PTAS for Identical Machines -- 5 EPTAS for Identical Machines -- References -- Streaming Algorithms for Bin Packing and Vector Scheduling -- 1 Introduction -- 1.1 Problems and Streaming Model -- 1.2 Our Results -- 2 Related Work -- 2.1 Bin Packing -- 2.2 Scheduling -- 3 Bin Packing -- 3.1 Processing the Stream and Rounding -- 3.2 Bin Packing and Quantile Summaries -- 4 Vector Scheduling -- References -- An Improved Upper Bound for the Ring Loading Problem -- 1 Introduction -- 2 Preliminaries

3 Improved Upper Bound -- 4 Bounds for Small Instances -- 5 Conclusions -- References -- Parallel Online Algorithms for the Bin Packing Problem -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work on Online Bin Packing -- 1.3 Related Work on Online Bin Packing with Advice -- 1.4 Related Work on Parallel Online Algorithms -- 2 Preliminaries -- 2.1 k-Copy Online Algorithms -- 2.2 Bin Packing -- 3 PREDICTIVE HARMONIC3 -- 3.1 Competitive Ratio -- 3.2 Tightness -- 4 Parallel PREDICTIVE HARMONIC3 -- 4.1 Competitive Ratio for PH3 as 1-Copy Online Algorithm

Description based on online resource; title from digital title page (viewed on April 09, 2020).