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-OzbMATH Open0778.68040MaRDI QIDQ1208477FDOQ1208477

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

Publication date: 16 May 1993

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

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

zbMATH Keywords

lower boundbin packing

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A simple on-line bin-packing algorithm
• A lower bound for on-line bin packing
• New Algorithms for Bin Packing
• A Tight Asymptotic Bound for Next-Fit-Decreasing 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)