An improved lower bound for on-line bin packing algorithms

DOI10.1016/0020-0190(92)90223-IMaRDI QIDQ1199958zbMATH OpenWikidataFDO

Authors André van Vliet

Publication date 17 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90223-I

zbMATH Keywords

bin packinglower boundon-line algorithm

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Improved lower bounds for semi-online bin packing problems
• Improved lower bounds for the online bin packing problem with cardinality constraints
• Improved lower bounds for the online bin packing problem with cardinality constraints
• A new lower bound for classic online bin packing
• A new lower bound for classic online bin packing
• Parametric Lower Bound for On-Line Bin-Packing
• Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
• Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing

Cites work

• A lower bound for on-line bin packing
• A simple on-line bin-packing algorithm
• A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case
• scientific article; zbMATH DE number 4154224 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On-line bin packing in linear time
• Parametric Lower Bound for On-Line Bin-Packing

Cited in

(86)

• Bin packing with controllable item sizes
• On-line grid-packing with a single active grid
• A robust APTAS for the classical bin packing problem
• Improved lower bounds for semi-online bin packing problems
• On dynamic bin packing: An improved lower bound and resource augmentation analysis
• 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
• Worst-case analysis of fast heuristics for packing squares into a square
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• Dynamic bin packing with unit fraction items revisited
• Tight bounds for NF-based bounded-space online bin packing algorithms
• The optimal absolute ratio for online bin packing
• Batched bin packing
• More on batched bin packing
• Performance analysis and improvement for some linear on-line bin-packing algorithms
• Two-dimensional on-line bin packing problem with rotatable items.
• Algorithms for on-line bin-packing problems with cardinality constraints
• More on ordered open end bin packing
• Lower bounds for batched bin packing
• Open-end bin packing: new and old analysis approaches
• Online bin packing with cardinality constraints resolved
• Efficient 1-space bounded hypercube packing algorithm
• On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis
• Fully dynamic bin packing revisited
• A lower bound for online rectangle packing
• Online results for black and white bin packing
• Improved lower bounds for the online bin packing problem with cardinality constraints
• Locality-preserving allocations problems and coloured bin packing
• Online bin packing with \((1,1)\) and \((2,R)\) bins
• Dynamic bin packing of unit fractions items
• Online algorithms for 1-space bounded multidimensional bin packing and hypercube packing
• Batched bin packing revisited
• Approximation and online algorithms for multidimensional bin packing: a survey
• Drawer algorithms for 1-space bounded multidimensional hyperbox packing
• Online bin packing with resource augmentation
• Improved results for a memory allocation problem
• Online bin packing with arbitrary release times
• The class constrained bin packing problem with applications to video-on-demand
• Bin packing problems with rejection penalties and their dual problems
• Online square and cube packing
• Approximate strip packing: revisited
• Bounds for online bin packing with cardinality constraints
• Parallel online algorithms for the bin packing problem
• Online Bin Packing with (1,1) and (2,R) Bins
• Shelf algorithms for on-line strip packing
• Improved Lower Bound for Online Strip Packing
• A survey on combinatorial optimization in dynamic environments
• Online algorithm for 1-space bounded multi-dimensional bin packing
• Semi-on-line bin packing: a short overview and a new lower bound
• Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing
• One-space bounded algorithms for two-dimensional bin packing
• Online Square Packing
• A new upper bound 2.5545 on 2D Online Bin Packing
• Better Algorithms for Online Bin Stretching
• Lower Bound for the Online Bin Packing Problem with Restricted Repacking
• Parametric Lower Bound for On-Line Bin-Packing
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations
• scientific article; zbMATH DE number 33204 (Why is no real title available?)
• Improved Space for Bounded-Space, On-Line Bin-Packing
• scientific article; zbMATH DE number 634028 (Why is no real title available?)
• New lower bounds for certain classes of bin packing algorithms
• Online square packing with gravity
• On-line bin packing ? A restricted survey
• A new and improved algorithm for online bin packing
• A tight lower bound for the online bounded space hypercube bin packing problem
• Online bin packing with cardinality constraints resolved
• On-line algorithms for packing rectangles into several strips
• Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
• Adaptive Bin Packing with Overflow
• Online bin packing of squares and cubes
• A new lower bound for classic online bin packing
• Several methods of analysis for cardinality constrained bin packing
• A new lower bound for classic online bin packing
• Online bin packing of squares and cubes
• Several methods of analysis for cardinality constrained bin packing
• A note on online hypercube packing
• Tighter bounds for the harmonic bin packing algorithm
• More on online cardinality constrained bin packing with small cardinality bounds
• An on-line algorithm for multidimensional bin packing
• Semi-online models for cardinality constrained bin packing
• Online algorithms for 1-space bounded 2-dimensional bin packing and square packing
• Bin packing with rejection revisited
• More on online bin packing with two item sizes
• Resource augmented semi-online bounded space bin packing
• Two-dimensional online bin packing with rotation
• Class constrained bin packing revisited

This page was built for publication: An improved lower bound for on-line bin packing algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199958)