Lower bounds for several online variants of bin packing
From MaRDI portal
Publication:5915655
DOI10.1007/978-3-319-89441-6_9zbMath1436.68401arXiv1708.03228OpenAlexW2964154102MaRDI QIDQ5915655
János Balogh, Leah Epstein, Asaf Levin, József Békési, György Dósa
Publication date: 22 June 2018
Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1708.03228
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items (15)
Lower bounds for batched bin packing ⋮ Lower bounds on the performance of online algorithms for relaxed packing problems ⋮ A note on a variant of the online open end bin packing problem ⋮ Online bin covering with limited migration ⋮ Efficient 1-space bounded hypercube packing algorithm ⋮ Online bin packing of squares and cubes ⋮ Online bin packing of squares and cubes ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ Online Bin Covering with Limited Migration ⋮ Lower bounds for online bin covering-type problems ⋮ Online bin covering with advice ⋮ More on ordered open end bin packing ⋮ A lower bound for online rectangle packing ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ A tight lower bound for the online bounded space hypercube bin packing problem
Cites Work
- Unnamed Item
- Unnamed Item
- Online bin packing with advice
- Semi-on-line bin packing: a short overview and a new lower bound
- New lower bounds for certain classes of bin packing algorithms
- Tight bounds for online class-constrained packing
- A note on online hypercube packing
- Class constrained bin packing revisited
- Multidimensional on-line bin packing: Algorithms and worst-case analysis
- A lower bound for on-line bin packing
- An improved lower bound for on-line bin packing algorithms
- Polynomial time approximation schemes for class-constrained packing problems
- New bounds for multidimensional packing
- Fast algorithms for bin packing
- Algorithms for on-line bin-packing problems with cardinality constraints
- Cardinality constrained bin-packing problems
- Improved lower bounds for the online bin packing problem with cardinality constraints
- The class constrained bin packing problem with applications to video-on-demand
- Online square and cube packing
- Bounds for online bin packing with cardinality constraints
- Robust Approximation Schemes for Cube Packing
- On Bin Packing with Conflicts
- Online Bin Packing with Advice of Small Size
- On the online bin packing problem
- New Algorithms for Bin Packing
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
- Beating the Harmonic Lower Bound for Online Bin Packing
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Online Bin Packing with Cardinality Constraints
- A new lower bound for classic online bin packing
This page was built for publication: Lower bounds for several online variants of bin packing
