Amazon cover image
Image from Amazon.com

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

By: (18th : WAOA (Workshop) (18th : 2020 : Online)Contributor(s): Kaklamanis, Christos | Levin, AsafMaterial type: TextTextSeries: Serienbezeichnung | Lecture notes in computer science ; 12806. | LNCS sublibrary. SL 1, Theoretical computer science and general issues.Publication details: Cham : Springer, 2021. Description: 1 online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9783030808792; 3030808793Other title: WAOA 2020Subject(s): Online algorithms -- Congresses | Approximation algorithms -- Congresses | Computer science -- Mathematics | Approximation algorithms | Computer science -- Mathematics | Online algorithmsGenre/Form: Electronic books. | Conference papers and proceedings. Additional physical formats: Print version:: Approximation and Online AlgorithmsDDC classification: 005.1 LOC classification: QA76.9.A43 | W36 2020ebOnline resources: Click here to access online
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
Summary: 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.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook Available
Total holds: 0

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

Powered by Koha