Approximation and online algorithms : 18th International Workshop, WAOA 2020, Virtual event, September 9-10, 2020, Revised Selected Papers

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

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 fro...

Full description

Saved in:
Bibliographic Details
Corporate Author: WAOA (Workshop) Online)
Other Authors: Kaklamanis, Christos, Levin, Asaf, 1974-
Format: eBook
Language:English
Published: Cham : Springer, 2021.
Series:Lecture notes in computer science ; 12806.
LNCS sublibrary. Theoretical computer science and general issues.
Subjects:
Online algorithms > Congresses.
Approximation algorithms > Congresses.
Computer science > Mathematics.
Approximation algorithms
Computer science > Mathematics
Online algorithms
Algorismes en línia.
Optimització matemàtica.
proceedings (reports)
Conference papers and proceedings
Conference papers and proceedings.
Actes de congrès.
Congressos.
Online Access:Click for online access
Table of Contents:
  • 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

Similar Items