Streaming algorithms for bin packing and vector scheduling

DOI10.1007/s00224-020-10011-yOpenAlexW2944742748MaRDI QIDQ5919096

Pavel Veselý, Graham Cormode

Publication date: 28 September 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10011-y

zbMATH Keywords

schedulingbin packingstreaming algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Related Items (2)

Streaming algorithms for multitasking scheduling with shared processing ⋮ Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• There is no asymptotic PTAS for two-dimensional vector packing
• New lower bounds for certain classes of bin packing algorithms
• Approximating vector scheduling: almost matching upper and lower bounds
• A sublinear-time approximation scheme for bin packing
• Bin packing can be solved within 1+epsilon in linear time
• Resource constrained scheduling as generalized bin packing
• On-line scheduling revisited
• Fast algorithms for bin packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing
• A Linear Programming Approach to the Cutting-Stock Problem
• Data Streams: Algorithms and Applications
• A simple on-line bin-packing algorithm
• Better Bounds for Online Scheduling
• Improved Approximation for Vector Bin Packing
• A Logarithmic Additive Integrality Gap for Bin Packing
• Tight Bounds for Online Vector Scheduling
• On Multidimensional Packing Problems
• Fully-Dynamic Bin Packing with Little Repacking
• The Moser--Tardos Framework with Partial Resampling
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• On the optimality of approximation schemes for the classical scheduling problem
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Tight bounds for online vector bin packing
• Streaming algorithms for bin packing and vector scheduling

This page was built for publication: Streaming algorithms for bin packing and vector scheduling