In 1996 Ivkovič and Lloyd [A fundamental restriction on fully dynamic maintenance of bin packing, Inform. Process. Lett., 59 (1996), pp. 229–232] gave the lower bound $\frac{4}{3}$ on the asymptotic worst-case ratio for so-called fully dynamic bin packing algorithms, where the number of repackable items in each step is restricted by a constant. In this paper we improve this result to about $1.3871$. We present our proof for a semionline case of the classical bin packing, but it works for fully dynamic bin packing as well. We prove the lower bound by analyzing and solving a specific optimization problem. The bound can be expressed exactly using the Lambert W function.

Previous article A Note on "An On-Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling"R. Chandrasekaran, Bo Chen, Gábor Galambos, P. R. Narayanan, André Van Vliet, and Gerhard J. WoegingerR. Chandrasekaran, Bo Chen, Gábor Galambos, P. R. Narayanan, André Van Vliet, and Gerhard J. Woegingerhttps://doi.org/10.1137/S0097539793258775PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] Google Scholar[2] Gábor Galambos and , Gerhard Woeginger, An on‐line scheduling heuristic with better worst‐case ratio than Graham’s list scheduling, SIAM J. Comput., 22 (1993), 349–355 94b:90031 LinkISIGoogle Scholar[3] Google ScholarKeywordscombinatorial problemsschedulingworst-case boundson-line algorithms Previous article FiguresRelatedReferencesCited ByDetails A survey on makespan minimization in semi-online environmentsJournal of Scheduling, Vol. 21, No. 3 | 13 April 2018 Cross Ref Scheduling Web Advertisements: A Note on the Minspace ProblemJournal of Scheduling, Vol. 8, No. 1 | 1 Jan 2005 Cross Ref On-line scheduling revisitedJournal of Scheduling, Vol. 3, No. 6 | 1 January 2000 Cross Ref Online Scheduling RevisitedAlgorithms - ESA 2000 | 11 February 2003 Cross Ref A Review of Machine Scheduling: Complexity, Algorithms and ApproximabilityHandbook of Combinatorial Optimization | 1 Jan 1998 Cross Ref Volume 26, Issue 3| 1997SIAM Journal on Computing605-872 History Published online:28 July 2006 InformationCopyright © 1997 Society for Industrial and Applied MathematicsKeywordscombinatorial problemsschedulingworst-case boundson-line algorithmsMSC codes90B3590C27PDF Download Article & Publication DataArticle DOI:10.1137/S0097539793258775Article page range:pp. 870-872ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

The problem of on-line scheduling a set of independent jobs on m machines is considered. The goal is to minimize the makespan of the schedule. Graham’s List Scheduling heuristic [R. L. Graham, SIAM J. Appl. Math., 17(1969), pp. 416–429] guarantees a worst case performance of $2 - \frac{1} {m}$ for this problem. This worst case bound cannot be improved for $m = 2$ and $m = 3$. For $m \geqslant 4$, approximation algorithms with worst case performance at most $2 - \frac{1}{m} - \varepsilon _m $ are presented, where $\varepsilon _m $ is some positive real depending only on m.