Approximation and Online Algorithms : 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised selected papers / Evripidis Bampis, Nicole Megow (eds.).

By: (17th : WAOA (Workshop) (17th : 2019 : Munich, Germany)
Contributor(s): Bampis, Evripidis | Megow, Nicole
Material type: TextTextSeries: SerienbezeichnungLecture notes in computer science: 11926.; LNCS sublibrary: Publisher: Cham, Switzerland : Springer, [2020]Description: 1 online resource (xii, 253 p.) : ill. (some col.)Content type: text Media type: computer Carrier type: online resourceISBN: 9783030394790; 3030394794Other title: WAOA 2019Subject(s): Online algorithms -- Congresses | Approximation algorithms -- Congresses | Computer science -- Mathematics | Approximation algorithms | Computer science -- Mathematics | Online algorithmsGenre/Form: Electronic books. | Electronic books. | Conference papers and proceedings. DDC classification: 005.1 | 518 LOC classification: QA76.9.A43 | W36 2019Online resources: Click here to access online
Contents:
Intro -- Preface -- Organization -- On the Hardness of Computing the Diameter of a Polytope (Invited Talk) -- Contents -- Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains -- 1 Introduction -- 2 A PTAS for Minimum Dominating Set in Terrain-Like Graphs -- 2.1 Algorithm -- 2.2 Analysis -- 2.3 Maximum Independent Set -- 3 Guarding the Vertices -- 3.1 x-monotone (1.5D) Terrains -- 3.2 WV-polygons -- 3.3 WV-terrains: Removing the Monotonicity Assumption -- 4 Guarding the Boundary -- 4.1 The Semi-continuous Version -- 4.2 The Continuous Version
5 Terrain-Like vs. Non-jumping -- References -- A New Lower Bound for Classic Online Bin Packing -- 1 Introduction -- 1.1 New Features of Our Work -- 2 The Input -- 3 Bounds on the Optimal Costs -- 4 An Analysis Using Weights -- 4.1 The Assignment of Weights to Items -- 4.2 Definition of Bin Types -- 4.3 The Price of a Bin Type -- 4.4 Calculating the Prices of the Bin Types -- 4.5 Using the Prices of Bin Types to Establish the Lower Bound on the Asymptotic Competitive Ratio -- References -- Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s, t)-Cuts
1 Introduction -- 2 Preliminaries -- 3 Competitive Ratio of Existing Strategies When max< k -- 4 Detour Strategy -- 4.1 Description of -Detour Strategy -- 4.2 Competitive Analysis -- 4.3 Discussion -- 5 Conclusion -- References -- Robust Online Algorithms for Certain Dynamic Packing Problems -- 1 Introduction -- 1.1 Related Works -- 1.2 Our Results -- 2 Online Algorithms for Dynamic Problems: A Framework -- 3 2-Dimensional Strip Packing -- 4 Bin Packing -- 5 Vector Packing -- References -- Approximation Results for Makespan Minimization with Budgeted Uncertainty -- 1 Introduction
2 A 3-Approximation for Unrelated Machines -- 3 A 2- Inapproximability for Unrelated Machines -- 4 A PTAS for Identical Machines -- 5 EPTAS for Identical Machines -- References -- Streaming Algorithms for Bin Packing and Vector Scheduling -- 1 Introduction -- 1.1 Problems and Streaming Model -- 1.2 Our Results -- 2 Related Work -- 2.1 Bin Packing -- 2.2 Scheduling -- 3 Bin Packing -- 3.1 Processing the Stream and Rounding -- 3.2 Bin Packing and Quantile Summaries -- 4 Vector Scheduling -- References -- An Improved Upper Bound for the Ring Loading Problem -- 1 Introduction -- 2 Preliminaries
3 Improved Upper Bound -- 4 Bounds for Small Instances -- 5 Conclusions -- References -- Parallel Online Algorithms for the Bin Packing Problem -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work on Online Bin Packing -- 1.3 Related Work on Online Bin Packing with Advice -- 1.4 Related Work on Parallel Online Algorithms -- 2 Preliminaries -- 2.1 k-Copy Online Algorithms -- 2.2 Bin Packing -- 3 PREDICTIVE HARMONIC3 -- 3.1 Competitive Ratio -- 3.2 Tightness -- 4 Parallel PREDICTIVE HARMONIC3 -- 4.1 Competitive Ratio for PH3 as 1-Copy Online Algorithm
Summary: This book constitutes the thoroughly refereed workshop post-proceedings of the 17th International Workshop on Approximation and Online Algorithms, WAOA 2019, held in Munich, Germany, in September 2019 as part of ALGO 2019. The 16 revised full papers presented together with one invited paper in this book were carefully reviewed and selected from 38 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; and real-world applications.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook Available
Total holds: 0

This book constitutes the thoroughly refereed workshop post-proceedings of the 17th International Workshop on Approximation and Online Algorithms, WAOA 2019, held in Munich, Germany, in September 2019 as part of ALGO 2019. The 16 revised full papers presented together with one invited paper in this book were carefully reviewed and selected from 38 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; and real-world applications.

Includes author index.

Intro -- Preface -- Organization -- On the Hardness of Computing the Diameter of a Polytope (Invited Talk) -- Contents -- Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains -- 1 Introduction -- 2 A PTAS for Minimum Dominating Set in Terrain-Like Graphs -- 2.1 Algorithm -- 2.2 Analysis -- 2.3 Maximum Independent Set -- 3 Guarding the Vertices -- 3.1 x-monotone (1.5D) Terrains -- 3.2 WV-polygons -- 3.3 WV-terrains: Removing the Monotonicity Assumption -- 4 Guarding the Boundary -- 4.1 The Semi-continuous Version -- 4.2 The Continuous Version

5 Terrain-Like vs. Non-jumping -- References -- A New Lower Bound for Classic Online Bin Packing -- 1 Introduction -- 1.1 New Features of Our Work -- 2 The Input -- 3 Bounds on the Optimal Costs -- 4 An Analysis Using Weights -- 4.1 The Assignment of Weights to Items -- 4.2 Definition of Bin Types -- 4.3 The Price of a Bin Type -- 4.4 Calculating the Prices of the Bin Types -- 4.5 Using the Prices of Bin Types to Establish the Lower Bound on the Asymptotic Competitive Ratio -- References -- Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s, t)-Cuts

1 Introduction -- 2 Preliminaries -- 3 Competitive Ratio of Existing Strategies When max< k -- 4 Detour Strategy -- 4.1 Description of -Detour Strategy -- 4.2 Competitive Analysis -- 4.3 Discussion -- 5 Conclusion -- References -- Robust Online Algorithms for Certain Dynamic Packing Problems -- 1 Introduction -- 1.1 Related Works -- 1.2 Our Results -- 2 Online Algorithms for Dynamic Problems: A Framework -- 3 2-Dimensional Strip Packing -- 4 Bin Packing -- 5 Vector Packing -- References -- Approximation Results for Makespan Minimization with Budgeted Uncertainty -- 1 Introduction

2 A 3-Approximation for Unrelated Machines -- 3 A 2- Inapproximability for Unrelated Machines -- 4 A PTAS for Identical Machines -- 5 EPTAS for Identical Machines -- References -- Streaming Algorithms for Bin Packing and Vector Scheduling -- 1 Introduction -- 1.1 Problems and Streaming Model -- 1.2 Our Results -- 2 Related Work -- 2.1 Bin Packing -- 2.2 Scheduling -- 3 Bin Packing -- 3.1 Processing the Stream and Rounding -- 3.2 Bin Packing and Quantile Summaries -- 4 Vector Scheduling -- References -- An Improved Upper Bound for the Ring Loading Problem -- 1 Introduction -- 2 Preliminaries

3 Improved Upper Bound -- 4 Bounds for Small Instances -- 5 Conclusions -- References -- Parallel Online Algorithms for the Bin Packing Problem -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work on Online Bin Packing -- 1.3 Related Work on Online Bin Packing with Advice -- 1.4 Related Work on Parallel Online Algorithms -- 2 Preliminaries -- 2.1 k-Copy Online Algorithms -- 2.2 Bin Packing -- 3 PREDICTIVE HARMONIC3 -- 3.1 Competitive Ratio -- 3.2 Tightness -- 4 Parallel PREDICTIVE HARMONIC3 -- 4.1 Competitive Ratio for PH3 as 1-Copy Online Algorithm

Description based on online resource; title from digital title page (viewed on April 09, 2020).

There are no comments for this item.

to post a comment.

Powered by Koha