Approximation and Online Algorithms : 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised selected papers /: 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised selected papers. ([2020])
- Record Type:
- Book
- Title:
- Approximation and Online Algorithms : 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised selected papers /: 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised selected papers. ([2020])
- Main Title:
- Approximation and Online Algorithms : 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised selected papers
- Other Titles:
- WAOA 2019
- Further Information:
- Note: Evripidis Bampis, Nicole Megow (eds.).
- Other Names:
- Bampis, Evripidis
Megow, Nicole
WAOA (Workshop), 17th - 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 WorksIntro -- 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 … (more)
- Publisher Details:
- Cham, Switzerland : Springer
- Publication Date:
- 2020
- Extent:
- 1 online resource, illustrations (colour)
- Subjects:
- 005.1
518
Online algorithms -- Congresses
Approximation algorithms -- Congresses
Computer science -- Mathematics
Approximation algorithms
Computer science -- Mathematics
Online algorithms
Electronic books
Electronic books
Conference papers and proceedings - Languages:
- English
- ISBNs:
- 9783030394790
3030394794
3030394786
9783030394783
9783030394806
3030394808 - Related ISBNs:
- 9783030394783
- Notes:
- Note: Description based on online resource; title from digital title page (viewed on April 09, 2020).
- Access Rights:
- Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
- Access Usage:
- Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD.DS.486694
- Ingest File:
- 03_044.xml