Approximation and Online Algorithms: 20th International Workshop, WAOA 2022, Potsdam, Germany, September 8–9, 2022, Proceedings (Lecture Notes in Computer Science, 13538)

Description

This book constitutes revised selected papers from the thoroughly refereed workshop proceedings of the 20th International Workshop on Approximation and Online Algorithms, WAOA 2022, which was colocated with ALGO 2022 and took place in Potsdam, Germany, in September 2022. The 12 papers included in these proceedings were carefully reviewed and selected from21 submissions. They focus on topics such as graph algorithms, network design, algorithmic game theory, approximation and online algorithms, etc. Preface Organization A PTAS for Unsplittable Flow on a Path (Invited Talk) Contents Locating Service and Charging Stations 1 Introduction 2 Preliminaries and Related Work 3 Locating Service Stations 3.1 Linear Program and the Integrality Gap 3.2 The Graph is a Tree 3.3 General Graphs 4 Locating Charging Stations for Given Source-Destination Pairs 4.1 The Graph is a Tree 4.2 General Graphs 5 Locating Charging Stations When Routes are Specified 5.1 The Graph is a Tree 5.2 General Graphs 6 Conclusion References Graph Burning and Non-uniform k-centers for Small Treewidth 1 Introduction 2 Solving k-center Problem with Different Radii on Trees 3 Generalization to Graphs with Small Treewidth 3.1 Tree Decompositions 3.2 Tidy Assignments 3.3 The Algorithm 4 A PTAS for Burning Graphs of Small Treewidth 5 Conclusions References Scheduling with Machine Conflicts 1 Introduction 1.1 Our Contribution and Organization 1.2 Related Work 2 Identical Jobs 3 Unit Jobs 3.1 Stars 3.2 Optimal Schedules for Bipartite Graphs for a Given Star Forest 3.3 Computing a Star Forest with I, II, III-Colorings 4 Future Directions 5 Appendix I – Details for Sect.2 5.1 Long Blocking Times 5.2 Short Blocking Times 6 Appendix II – Details for Sect.3 References Knapsack Secretary Through Boosting 1 Introduction 1.1 Related Work 1.2 Our Contribution 2 Preliminaries 3 Matching 1/e for 1–2-Knapsack 3.1 Structural Lemma 3.2 First Approach: Without Boosting 3.3 Optimal Algorithm Through -Boosting 4 Ordinal Algorithms for 1-B-Knapsack 5 Conclusion References Scheduling Appointments Online: The Power of Deferred Decision-Making 1 Introduction 2 Packing Algorithm 2.1 Schedule Creation 2.2 Rematching 2.3 Example Category Packing 3 Analysis 3.1 Properties 3.2 Configuration Bin-Packing LP 3.3 Additive Constants Bins 3.4 Bounded Imbalanced Bins 3.5 Multiplicative Bound on Packed Bins 3.6 Completing the Proof of Theorem 1 4 Lower Bounds 4.1 Deterministic Lower Bound 4.2 Randomized Lower Bound 5 Conclusions and Future Work A Particularly Hard Input B Configuration Strategies B.1 Alternating Sides B.2 Type 2 Small Bins B.3 Rematching with Different Large Item Categories B.4 Rematching with Quarter Item Sets B.5 Rematching with Large Items C Category List and Matching Process Description C.1 Very Large Items C.2 Large Items C.3 Medium Items C.4 Third Items C.5 Small Items References Canadian Traveller Problem with Predictions 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Deterministic and Randomized Algorithms 2.2 Notations 3 Tradeoffs Between Consistency and Robustness 3.1 Tradeoffs for Deterministic Algorithms 3.2 Randomized Bounds and Algorithms 4 Robustness Analysis 4.1 Deterministic Bounds 4.2 Randomized Bounds References The Power of Amortized Recourse for Online Graph Problems 1 Introduction 2 Monotone-Sum Graph Problems and a General Algorithm 3 Maximum Independent Set 4 Maximum Cardinality Matching 5 Minimum Vertex Cover 6 Concluding Remarks References An Improved Algorithm for Open Online Dial-a-Ride 1 Introduction 2 Notation and Definition of the Algorithm 3 Analysis of Lazy 4 Lower Bound for Lazy References Stochastic Graph Exploration with Limited Resources 1 Introduction 1.1 Summary of Results and Techniques 1.2 Related Work 2 Preliminaries 3 Bounding the Optimal Adaptive Policy 4 Spider Graphs 4.1 Non-adaptive Algorithm 4.2 Risky Vertices 4.3 Non-risky Vertices 4.4 Putting Things Together 5 Bounded Weighted Depth Trees Instances 6 Examples References Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem 1 Introduction 1.1 Connection to st-Connectivity in Uncertain Networks 1.2 Related Work 1.3 Preliminaries 2 Warm Up: Adaptivity Gaps for Read-Once DNFs 2.1 Unit Costs and the Uniform Distribution 2.2 Unit Costs and Arbitrary Probabilities 2.3 Arbitrary Costs and the Uniform Distribution 3 Main Result: Read-Once Formulas 4 DNF Formulas 5 Conclusion and Open Problems A Additional Proofs References On Streaming Algorithms for Geometric Independent Set and Clique 1 Introduction 1.1 Our Results 2 Independent Sets in Streams of Segments 3 Intervals and Segments are Different 4 Independent Sets in Streams of c-Intervals 5 Independent Sets in Streams of Unit-Height Rectangles 6 Clique in Streams of Intervals and Segments 7 Conclusion References Approximating Length-Restricted Means Under Dynamic Time Warping 1 Introduction 1.1 Related Work 1.2 Overview of Results 1.3 Preliminaries 2 Tractability of the Restricted Mean Problem 2.1 Exact Computation of a Restricted 2-Mean in Euclidean Space 2.2 Constant-Factor Approximation of the Restricted p-Mean 2.3 Simplifications and the Triangle Inequality 2.4 Approximation Scheme for Point Sequences in Euclidean Spaces 3 Application to Clustering 3.1 (k,,p,p)-Clustering 3.2 k-medians Under p-DTW 4 Conclusions References Author Index