Approximation and online algorithms : 18th International Workshop, WAOA 2020, Virtual event, September 9-10, 2020, Revised Selected Papers / Christos Kaklamanis, Asaf Levin (eds.).

Intro -- Preface -- Organization -- Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators (Invited Talk) -- Contents -- LP-Based Algorithms for Multistage Minimization Problems -- 1 Introduction -- 2 Rounding Scheme for Some Prize-Collecting Problems -- 2.1 Rounding Scheme -- 2.2 Prize-Collecting Steiner Tree -- 2.3 Prize-Collecting Metric Traveling Salesman -- 3 Min Cut, Vertex Cover and IP2 Linear Problems -- References -- A Faster FPTAS for Knapsack Problem with Cardinality Constraint -- 1 Introduction -- 1.1 Theoretical Motivations and Contributions

1.2 Technique Overview -- 2 Item Preprocessing -- 3 Algorithm for Large Items -- 3.1 An Abstract Algorithm Based on Convolution -- 3.2 Discretizing the Function Domain -- 3.3 Fast Convolution Algorithm -- 4 Continuous Relaxation for Small Items -- 4.1 Continuous Relaxation Design and Error Analysis -- 4.2 Computing ""0365S Efficiently -- 5 Putting the Pieces Together-Combining Small and Large Items -- 6 Conclusion -- References -- Distributed Algorithms for Matching in Hypergraphs -- 1 Introduction -- 2 Our Contribution and Results -- 3 Related Work -- 4 A 3-Round O(d2)-Approximation

5 A O(logn)-Rounds d-Approximation Algorithm -- 6 A 3-Round O(d3)-Approximation Using HEDCSs -- 6.1 Sampling and Constructing an HEDCS in the MPC Model -- 7 Computational Experiments -- 7.1 Experiments with Random Uniform Hypergraphs -- 7.2 Experiments with Real Data -- 7.3 Experimental Conclusions -- 8 Conclusion -- References -- Online Coloring and a New Type of Adversary for Online Graph Problems -- 1 Introduction -- 2 Preliminaries -- 2.1 Bins Vs. Colors -- 2.2 Saturated Bins -- 3 A New Type of Adversary -- 4 FirstFit on -colorable Graphs, Triangle-Free Graphs, and Trees

5 CBIP on Bipartite Graphs -- 6 Lower Bounds for Several Graph Classes -- 7 Conclusion and Open Problems -- References -- Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique -- 1 Introduction -- 2 Preliminaries -- 3 Maximum Coverage with Knapsack Constraints -- 4 Maximum Coverage with Cluster Constraints -- 5 Multiple Knapsack with Cluster Constraints -- 5.1 13-Approximation for MKPC with General Clusters -- 5.2 12-Approximation for MKPC with Isolation Property -- References -- A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon -- 1 Introduction

2 Structural Analysis -- 2.1 Visibility Polygons -- 2.2 Pockets -- 2.3 Holes -- 3 The Algorithm -- 4 Polygons Weakly Visible from a Chord -- References -- Lasserre Integrality Gaps for Graph Spanners and Related Problems -- 1 Introduction -- 1.1 Our Results and Techniques -- 2 Preliminaries: Lasserre Hierarchy -- 3 Projection Games: Background and Previous Work -- 4 Lasserre Integrality Gap for Directed (2k-1)-Spanner -- 4.1 Spanner LPs and Their Lasserre Lifts -- 4.2 Spanner Instance -- 4.3 Fractional Solution -- 4.4 Proof of Theorem 1 -- 5 Undirected (2k-1)-Spanner -- References

To Close Is Easier Than To Open: Dual Parameterization To k-Median.

This book constitutes the thoroughly refereed workshop post-proceedings of the 18th International Workshop on Approximation and Online Algorithms, WAOA 2019, held virtually in September 2020 as part of ALGO 2020. The 15 revised full papers presented this book were carefully reviewed and selected from 40 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, real-world applications. Chapter "Explorable Uncertainty in Scheduling with Non-Uniform Testing Times" is available open access under a Creative Commons Attribution 4.0 International License via link.springer.com.

Includes author index.

Online resource; title from PDF title page (SpringerLink, viewed July 21, 2021).