Editing Bin packing problem (section)

=== General lower bounds for online algorithms ===
Yao<ref name="Yao19802" /> proved in 1980 that there can be no online algorithm with an asymptotic competitive ratio smaller than <math>\tfrac 3 2</math>. Brown<ref>{{cite journal|last1=Donna J|first1=Brown|date=1979|title=A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms.|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a085315.pdf|archive-url=https://web.archive.org/web/20220317212050/https://apps.dtic.mil/dtic/tr/fulltext/u2/a085315.pdf|url-status=live|archive-date=March 17, 2022|journal=Technical Rept.}}</ref> and Liang<ref>{{cite journal|last1=Liang|first1=Frank M.|date=1980|title=A lower bound for on-line bin packing|journal=Information Processing Letters|volume=10|issue=2|pages=76–79|doi=10.1016/S0020-0190(80)90077-0}}</ref> improved this bound to {{val|1.53635}}. Afterward, this bound was improved to {{val|1.54014}} by Vliet.<ref>{{cite journal|last1=van Vliet|first1=André|date=1992|title=An improved lower bound for on-line bin packing algorithms|journal=Information Processing Letters|volume=43|issue=5|pages=277–284|doi=10.1016/0020-0190(92)90223-I}}</ref>  In 2012, this lower bound was again improved by Békési and Galambos<ref>{{cite journal|last1=Balogh|first1=János|last2=Békési|first2=József|last3=Galambos|first3=Gábor|date=July 2012|title=New lower bounds for certain classes of bin packing algorithms|journal=Theoretical Computer Science|volume=440–441|pages=1–13|doi=10.1016/j.tcs.2012.04.017|doi-access=free}}</ref> to <math>\tfrac {248}{161} \approx 1.54037</math>.