A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case

DOI10.1016/0166-218X(93)90037-OMaRDI QIDQ1208477zbMATH OpenFDO

Authors J. B. G. Frenk, Gábor Galambos

Publication date 16 May 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

lower boundbin packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40)

Recommendations

• An improved lower bound for on-line bin packing algorithms
• 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
• New Lower Bounds for Certain Classes of Bin Packing Algorithms

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
• A lower bound for on-line bin packing
• A simple on-line bin-packing algorithm
• New Algorithms for Bin Packing
• Parametric Lower Bound for On-Line Bin-Packing

Cited in

(7)

• New lower bounds for certain classes of bin packing algorithms
• A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
• An improved lower bound for on-line bin packing algorithms
• On-line bin packing ? A restricted survey
• Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
• Online square packing with gravity
• Parametric Lower Bound for On-Line Bin-Packing

This page was built for publication: A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case

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