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