AN IMPROVED LOWER BOUND FOR ONLINE BIN PACKING ALGORITHMS

被引：121
|
作者：
VANVLIET, A
机构：
[1] ERASMUS UNIV,INST TINBERGEN,3000 DR ROTTERDAM,NETHERLANDS
[2] ATTILA JOZSEF UNIV,H-6701 SZEGED,HUNGARY
来源：
INFORMATION PROCESSING LETTERS | 1992年 / 43卷 / 05期
关键词：
BIN PACKING; LOWER BOUNDS; ONLINE ALGORITHMS; COMBINATORIAL PROBLEMS;
D O I：
10.1016/0020-0190(92)90223-I
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In 1980 Liang proved that every on-line algorithm for the bin packing problem has an asymptotic worst case ratio of at least 1.536.... In this paper we give an improved lower bound of 1.540.... For the parametric case where all items are smaller than or equal to 1/r, r is-an-element-of N+, we also give improved lower bounds.
引用
收藏
页码：277 / 284
页数：8
相关论文
共 50 条
  • [21] A tight lower bound for optimal bin packing
    Chao, HY
    Harper, MP
    Quong, RW
    OPERATIONS RESEARCH LETTERS, 1995, 18 (03) : 133 - 138
  • [22] Comparing online algorithms for bin packing problems
    Leah Epstein
    Lene M. Favrholdt
    Jens S. Kohrt
    Journal of Scheduling, 2012, 15 : 13 - 21
  • [23] Parallel Online Algorithms for the Bin Packing Problem
    Fekete, Sandor P.
    Grosse-Holz, Jonas
    Keldenich, Phillip
    Schmidt, Arne
    ALGORITHMICA, 2023, 85 (01) : 296 - 323
  • [24] Parallel Online Algorithms for the Bin Packing Problem
    Fekete, Sandor P.
    Grosse-Holz, Jonas
    Keldenich, Phillip
    Schmidt, Arne
    APPROXIMATION AND ONLINE ALGORITHMS (WAOA 2019), 2020, 11926 : 106 - 119
  • [25] ONLINE ALGORITHMS FOR A DUAL VERSION OF BIN PACKING
    CSIRIK, J
    TOTIK, V
    DISCRETE APPLIED MATHEMATICS, 1988, 21 (02) : 163 - 167
  • [26] Parallel Online Algorithms for the Bin Packing Problem
    Sándor P. Fekete
    Jonas Grosse-Holz
    Phillip Keldenich
    Arne Schmidt
    Algorithmica, 2023, 85 : 296 - 323
  • [27] Comparing online algorithms for bin packing problems
    Epstein, Leah
    Favrholdt, Lene M.
    Kohrt, Jens S.
    JOURNAL OF SCHEDULING, 2012, 15 (01) : 13 - 21
  • [28] A SIMPLE PROOF OF LIANG LOWER BOUND FOR ONLINE BIN PACKING AND THE EXTENSION TO THE PARAMETRIC CASE
    GALAMBOS, G
    FRENK, JBG
    DISCRETE APPLIED MATHEMATICS, 1993, 41 (02) : 173 - 178
  • [29] Improved Approximation Algorithms for Bin Packing with Conflicts
    Huang, Zhihua
    Zhang, An
    Dosa, Gyorgy
    Chen, Yong
    Xiong, Chenling
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2023,
  • [30] Lower bound for 3-batched bin packing
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    Dosa, Gyorgy
    Tan, Zhiyi
    DISCRETE OPTIMIZATION, 2016, 21 : 14 - 24
12345