Improved lower bounds for semi-online bin packing problems

被引：4
作者：
Balogh, Janos [3 ]
Bekesi, Jozsef [3 ]
Galambos, Gabor [3 ]
Markot, Mihaly Csaba [1 ,2 ]
机构：
[1] Univ Vienna, Fac Math, A-1090 Vienna, Austria
[2] European Space Agcy, Estec, Adv Concepts Team, Noordwijk, Netherlands
[3] Univ Szeged, Dept Informat Applicat, Gyula Juhasz Fac Educ, H-6725 Szeged, Hungary
来源：
COMPUTING | 2009年 / 84卷 / 1-2期
基金：
奥地利科学基金会;
关键词：
Semi-online bin packing problems; Nonlinear optimization; Branch-and-bound; Interval arithmetic;
D O I：
10.1007/s00607-008-0023-6
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In the paper we deal with lower bounds constructed for the asymptotic competitive ratio of semi-online bin packing and batched bin packing algorithms.We determine the bounds as the solutions of a related nonlinear optimization problem using theoretical analysis and a reliable numerical global optimization method. Our results improve the lower bounds given in Gutin et al. (Discrete Optim 2:71-82, 2005) for some special cases of the batched bin packing problem.
引用
收藏
页码：139 / 148
页数：10
相关论文
共 21 条
  • [1] [Anonymous], 1992, Global optimization using interval analysis
  • [2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
  • [3] [Anonymous], NUMERICAL TOOLBOX VE
  • [4] Lower bound for the online bin packing problem with restricted repacking
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    Reinelt, Gerhard
    [J]. SIAM JOURNAL ON COMPUTING, 2008, 38 (01) : 398 - 410
  • [5] Coffman E. G., 1999, HDB COMBINATORIAL OP, P151
  • [6] DYNAMIC BIN PACKING
    COFFMAN, EG
    GAREY, MR
    JOHNSON, DS
    [J]. SIAM JOURNAL ON COMPUTING, 1983, 12 (02) : 227 - 258
  • [7] Csirik J, 1998, LECT NOTES COMPUT SC, V1442, P147, DOI 10.1007/BFb0029568
  • [8] More on online bin packing with two item sizes
    Epstein, Leah
    Levin, Asaf
    [J]. DISCRETE OPTIMIZATION, 2008, 5 (04) : 705 - 713
  • [9] REPACKING HELPS IN BOUNDED SPACE ONLINE BIN-PACKING
    GALAMBOS, G
    WOEGINGER, GJ
    [J]. COMPUTING, 1993, 49 (04) : 329 - 338
  • [10] Algorithms for the relaxed online bin-packing model
    Gambosi, G
    Postiglione, A
    Talamo, M
    [J]. SIAM JOURNAL ON COMPUTING, 2000, 30 (05) : 1532 - 1551
123