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

zbMATH Keywords

lower boundbin packingon-line algorithmworst-case behavior

Mathematics Subject Classification ID

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)