An 8/3 Lower Bound for Online Dynamic Bin Packing

被引:0
|
作者
Wong, Prudence W. H. [1 ]
Yung, Fencol C. C. [1 ]
Burcea, Mihai [1 ]
机构
[1] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England
来源
ALGORITHMS AND COMPUTATION, ISAAC 2012 | 2012年 / 7676卷
关键词
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the dynamic bin packing problem introduced by Coffman, Garey and Johnson. This problem is a generalization of the bin packing problem in which items may arrive and depart dynamically. The objective is to minimize the maximum number of bins used over all time. The main result is a lower bound of 8/3 similar to 2.666 on the achievable competitive ratio, improving the best known 2.5 lower bound. The previous lower bounds were 2.388, 2.428, and 2.5. This moves a big step forward to close the gap between the lower bound and the upper bound, which currently stands at 2.788. The gap is reduced by about 60% from 0.288 to 0.122. The improvement stems from an adversarial sequence that forces an online algorithm A to open 2s bins with items having a total size of s only and this can be adapted appropriately regardless of the current load of other bins that have already been opened by A. Comparing with the previous 2.5 lower bound, this basic step gives a better way to derive the complete adversary and a better use of items of slightly different sizes leading to a tighter lower bound. Furthermore, we show that the 2.5-lower bound can be obtained using this basic step in a much simpler way without case analysis.
引用
收藏
页码:44 / 53
页数:10
相关论文
共 50 条
  • [1] A LOWER BOUND FOR ONLINE BIN PACKING
    LIANG, FM
    INFORMATION PROCESSING LETTERS, 1980, 10 (02) : 76 - 79
  • [2] 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
  • [3] PARAMETRIC LOWER BOUND FOR ONLINE BIN-PACKING
    GALAMBOS, G
    SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (03): : 362 - 367
  • [4] 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
  • [5] AN IMPROVED LOWER BOUND FOR ONLINE BIN PACKING ALGORITHMS
    VANVLIET, A
    INFORMATION PROCESSING LETTERS, 1992, 43 (05) : 277 - 284
  • [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] 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
  • [8] Lower bound for 3-batched bin packing
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    Dosa, Gyorgy
    Tan, Zhiyi
    DISCRETE OPTIMIZATION, 2016, 21 : 14 - 24
  • [9] On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis
    Joseph Wun-Tat Chan
    Prudence W. H. Wong
    Fencol C. C. Yung
    Algorithmica, 2009, 53 : 172 - 206
  • [10] On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis
    Chan, Joseph Wun-Tat
    Wong, Prudence W. H.
    Yung, Fencol C. C.
    ALGORITHMICA, 2009, 53 (02) : 172 - 206