New lower bounds for certain classes of bin packing algorithms
DOI10.1016/J.TCS.2012.04.017zbMATH Open1247.68339OpenAlexW2098705232MaRDI QIDQ441876FDOQ441876
Authors: János Balogh, József Békési, Gábor Galambos
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
Recommendations
- New Lower Bounds for Certain Classes of Bin Packing Algorithms
- scientific article; zbMATH DE number 1187157
- New classes of fast lower bounds for bin packing problems
- New bin packing fast lower bounds
- An improved lower bound for the bin packing problem
- A new lower bound for classic online bin packing
- A new lower bound for classic online bin packing
- A tight lower bound for optimal bin packing
- Lower bounds for batched bin packing
- Lower bounds and reduction procedures for the bin packing problem
Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Discrete location and assignment (90B80)
Cites Work
- Title not available (Why is that?)
- On the online bin packing problem
- A lower bound for on-line bin packing
- An improved lower bound for on-line bin packing algorithms
- Fast algorithms for bin packing
- Title not available (Why is that?)
- Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
- New Bounds for Variable-Sized Online Bin Packing
- A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case
- Title not available (Why is that?)
Cited In (50)
- Tighter bounds for the harmonic bin packing algorithm
- Online bin packing with advice of small size
- A new lower bound on the price of anarchy of selfish bin packing
- Online results for black and white bin packing
- Batched bin packing revisited
- Several methods of analysis for cardinality constrained bin packing
- Several methods of analysis for cardinality constrained bin packing
- Online bin packing with advice
- Semi-on-line bin packing: a short overview and a new lower bound
- Colored bin packing: online algorithms and lower bounds
- Online algorithms with advice for bin packing and scheduling problems
- A new and improved algorithm for online bin packing
- Online bin packing with advice of small size
- Black and White Bin Packing Revisited
- Online bin packing of squares and cubes
- The optimal absolute ratio for online bin packing
- The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
- Lower bound for 3-batched bin packing
- More on batched bin packing
- Adaptive Bin Packing with Overflow
- Streaming algorithms for bin packing and vector scheduling
- Locality-preserving allocations problems and coloured bin packing
- Lower bounds for batched bin packing
- Lower bounds for several online variants of bin packing
- Approximation and online algorithms for multidimensional bin packing: a survey
- A new lower bound for classic online bin packing
- A new lower bound for classic online bin packing
- Online bin packing with cardinality constraints resolved
- Improved bounds for harmonic-based bin packing algorithms
- Online bin packing of squares and cubes
- New Lower Bounds for Certain Classes of Bin Packing Algorithms
- Online bin packing with cardinality constraints resolved
- More on ordered open end bin packing
- Lower bounds on the performance of online algorithms for relaxed packing problems
- Fully-dynamic bin packing with little repacking
- Lower bounds and reduction procedures for the bin packing problem
- Open-end bin packing: new and old analysis approaches
- Online strip packing with polynomial migration
- Improved lower bounds for the online bin packing problem with cardinality constraints
- A tight lower bound for the online bounded space hypercube bin packing problem
- Online colored bin packing
- A lower bound for online rectangle packing
- Online two-dimensional vector packing with advice
- Bounds for online bin packing with cardinality constraints
- Bin packing problem with scenarios
- Online bin packing problem with buffer and bounded size revisited
- Tight bounds for NF-based bounded-space online bin packing algorithms
- A note on a variant of the online open end bin packing problem
- Title not available (Why is that?)
- Bin packing with ``largest in bottom constraint: tighter bounds and generalizations
This page was built for publication: New lower bounds for certain classes of bin packing algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441876)