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