New lower bounds for certain classes of bin packing algorithms
From MaRDI portal
Publication:441876
DOI10.1016/J.TCS.2012.04.017zbMath1247.68339OpenAlexW2098705232MaRDI QIDQ441876
Gábor Galambos, József Békési, János Balogh
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.017
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items (42)
Lower bounds for batched bin packing ⋮ Online Bin Packing with Advice of Small Size ⋮ Semi-on-line bin packing: a short overview and a new lower bound ⋮ Bounds for online bin packing with cardinality constraints ⋮ The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints ⋮ Online Colored Bin Packing ⋮ Black and White Bin Packing Revisited ⋮ Batched bin packing revisited ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Lower bounds on the performance of online algorithms for relaxed packing problems ⋮ Open-end bin packing: new and old analysis approaches ⋮ A note on a variant of the online open end bin packing problem ⋮ Online bin packing with cardinality constraints resolved ⋮ Bin packing problem with scenarios ⋮ Unnamed Item ⋮ Colored bin packing: online algorithms and lower bounds ⋮ Online two-dimensional vector packing with advice ⋮ Tight bounds for NF-based bounded-space online bin packing algorithms ⋮ Unnamed Item ⋮ Fully-Dynamic Bin Packing with Little Repacking ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ Online bin packing of squares and cubes ⋮ The optimal absolute ratio for online bin packing ⋮ Online bin packing problem with buffer and bounded size revisited ⋮ Lower bound for 3-batched bin packing ⋮ Online bin packing of squares and cubes ⋮ Lower bounds for several online variants of bin packing ⋮ More on batched bin packing ⋮ A new lower bound for classic online bin packing ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Unnamed Item ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ More on ordered open end bin packing ⋮ Online bin packing with advice of small size ⋮ A lower bound for online rectangle packing ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Online results for black and white bin packing ⋮ Adaptive Bin Packing with Overflow ⋮ A tight lower bound for the online bounded space hypercube bin packing problem ⋮ Improved lower bounds for the online bin packing problem with cardinality constraints ⋮ Locality-preserving allocations problems and coloured bin packing ⋮ Online bin packing with advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for on-line bin packing
- An improved lower bound for on-line bin packing algorithms
- A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case
- Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
- Fast algorithms for bin packing
- On the online bin packing problem
- New Bounds for Variable-Sized Online Bin Packing
This page was built for publication: New lower bounds for certain classes of bin packing algorithms
