Approximation and Online Algorithms: 18th International Workshop, WAOA 2020, Virtual Event, September 9–10, 2020, Revised Selected Papers

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
1 Introduction
2 Preliminaries
3 Uncapacitated Co--Median
4 Hardness of Capacitated co–Median
5 Conclusions and Open Problems
References
Explorable Uncertainty in Scheduling with Non-uniform Testing Times
1 Introduction
1.1 Problem Statement
1.2 Related Work
1.3 Contribution
2 Deterministic Setting
2.1 Basic Algorithm and Proof of 4-Competitiveness
2.2 A Deterministic Algorithm with Preemption
3 Randomized Setting
4 Optimal Results for Minimizing the Makespan
5 Conclusion
References
Memoryless Algorithms for the Generalized k-server Problem on Uniform Metrics
1 Introduction
1.1 Our Results
1.2 Notation and Preliminaries
2 Upper Bound
2.1 Definition of the Potential Function
2.2 Bounding the Competitive Ratio
3 Lower Bound
3.1 Constructing the Adversarial Instance
3.2 Proving the Lower Bound
4 Concluding Remarks
References
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
1 Introduction
1.1 Related Work
1.2 Organization
2 Hardness of Set Cover
2.1 Label Cover
2.2 Set Cover Reduction
2.3 Approximation Hardness Results
3 Proof of the Set Cover Reduction
3.1 Proof of Lemma 1
3.2 Proof of Lemma 2
4 Approximation Algorithm for Directed Steiner Tree
References
Concave Connection Cost Facility Location and the Star Inventory Routing Problem
1 Introduction
1.1 Previous Work
1.2 Nondecreasing Concave Connection Costs
1.3 Our Results
2 JMS with Penalties
2.1 Analysis: Factor-Revealing Program
2.2 Reducing the Factor Revealing Programs
3 Combining Algorithms for FLP
4 Solving NCC-FL with Algorithms for FLP
5 Approximation Algorithms for SIRPFL
References
An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem
1 Introduction
1.1 Our Contribution
2 Hardness of the Spanning Tree Case
3 Approximation Factors from Shallow-Light Steiner Trees
4 Improved Approximation for the Uniform Cost-Distance Steiner Tree Problem
5 Bounded-Ratio Cost-Distance Steiner Trees
6 Application: Delay Constrained Steiner Netlists
7 Conclusion
References
A Constant-Factor Approximation Algorithm for Red-Blue Set Cover with Unit Disks
1 Introduction
2 Polynomial-Time Algorithm for Line-Separable Red-Blue Set Cover
2.1 Statement of Block Decomposition Theorem
2.2 Sweep-Line Method
3 2-Factor Algorithm for Strip-Separable Red-Blue Set Cover
4 Red-Blue Set Cover with Unit Disks
References
2-Node-Connectivity Network Design
1 Introduction
2 Two Simple Reductions
2.1 Reduction to the Augmentation Problem
2.2 Reduction to Node Weighted Steiner Tree
3 Applications
3.1 Block-Tree Augmentation
3.2 2-Connected Dominating Set
3.3 2-Connected k-Subgraph
3.4 2-Connected Quota Subgraph
4 Crossing Family Augmentation
References
Author Index