A lower bound for on-line bin packing
From MaRDI portal
Publication:1144944
DOI10.1016/S0020-0190(80)90077-0zbMath0444.68061OpenAlexW2055872862WikidataQ29544691 ScholiaQ29544691MaRDI QIDQ1144944
Publication date: 1980
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(80)90077-0
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)
Related Items
Lower bounds for batched bin packing ⋮ Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms ⋮ Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time ⋮ Bounds for online bin packing with cardinality constraints ⋮ The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints ⋮ On two dimensional packing ⋮ Parametric Lower Bound for On-Line Bin-Packing ⋮ The average-case analysis of some on-line algorithms for bin packing ⋮ Online variable-sized bin packing ⋮ Online algorithms for a dual version of bin packing ⋮ Multidimensional on-line bin packing: Algorithms and worst-case analysis ⋮ On-line bin packing ? A restricted survey ⋮ A note on online hypercube packing ⋮ Drawer algorithms for 1-space bounded multidimensional hyperbox packing ⋮ Online bin packing with resource augmentation ⋮ Efficient 1-space bounded hypercube packing algorithm ⋮ On-line bin packing with restricted repacking ⋮ New lower bounds for certain classes of bin packing algorithms ⋮ Parallel online algorithms for the bin packing problem ⋮ Tight Bounds for Restricted Grid Scheduling ⋮ Improved bounds for harmonic-based bin packing algorithms ⋮ A fundamental restriction on fully dynamic maintenance of bin packing ⋮ Online bin packing of squares and cubes ⋮ More on online bin packing with two item sizes ⋮ Does randomization help in on-line bin packing? ⋮ An improved lower bound for on-line bin packing algorithms ⋮ An on-line algorithm for multidimensional bin packing ⋮ On-line scheduling of two parallel machines with a single server ⋮ A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case ⋮ Online bin packing of squares and cubes ⋮ Batched bin packing ⋮ Lower bounds for several online variants of bin packing ⋮ Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem ⋮ An on-line algorithm for variable-sized bin packing ⋮ Fully dynamic bin packing revisited ⋮ A new lower bound for classic online bin packing ⋮ Bounds for Scheduling Jobs on Grid Processors ⋮ Online square and cube packing ⋮ Two-dimensional rectangle packing: On-line methods and results ⋮ Online Bin Packing with (1,1) and (2,R) Bins ⋮ Online bin packing with \((1,1)\) and \((2,R)\) bins
Cites Work
This page was built for publication: A lower bound for on-line bin packing
