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 条
  • [1] A LOWER BOUND FOR ONLINE BIN PACKING
    LIANG, FM
    INFORMATION PROCESSING LETTERS, 1980, 10 (02) : 76 - 79
  • [2] An improved lower bound for the bin packing problem
    Chen, BT
    Srivastava, B
    DISCRETE APPLIED MATHEMATICS, 1996, 66 (01) : 81 - 94
  • [3] A New Lower Bound for Classic Online Bin Packing
    János Balogh
    József Békési
    György Dósa
    Leah Epstein
    Asaf Levin
    Algorithmica, 2021, 83 : 2047 - 2062
  • [4] PARAMETRIC LOWER BOUND FOR ONLINE BIN-PACKING
    GALAMBOS, G
    SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (03): : 362 - 367
  • [5] A New Lower Bound for Classic Online Bin Packing
    Balogh, Janos
    Bekesi, Jozsef
    Dosa, Gyorgy
    Epstein, Leah
    Levin, Asaf
    APPROXIMATION AND ONLINE ALGORITHMS (WAOA 2019), 2020, 11926 : 18 - 28
  • [6] A New Lower Bound for Classic Online Bin Packing
    Balogh, Janos
    Bekesi, Jozsef
    Dosa, Gyorgy
    Epstein, Leah
    Levin, Asaf
    ALGORITHMICA, 2021, 83 (07) : 2047 - 2062
  • [7] Colored Bin Packing: Online Algorithms and Lower Bounds
    Bohm, Martin
    Dosa, Gyorgy
    Epstein, Leah
    Sgall, Jiri
    Vesely, Pavel
    ALGORITHMICA, 2018, 80 (01) : 155 - 184
  • [8] Colored Bin Packing: Online Algorithms and Lower Bounds
    Martin Böhm
    György Dósa
    Leah Epstein
    Jiří Sgall
    Pavel Veselý
    Algorithmica, 2018, 80 : 155 - 184
  • [9] Lower bound for the online bin packing problem with restricted repacking
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    Reinelt, Gerhard
    SIAM JOURNAL ON COMPUTING, 2008, 38 (01) : 398 - 410
  • [10] An 8/3 Lower Bound for Online Dynamic Bin Packing
    Wong, Prudence W. H.
    Yung, Fencol C. C.
    Burcea, Mihai
    ALGORITHMS AND COMPUTATION, ISAAC 2012, 2012, 7676 : 44 - 53
12345