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 条
  • [31] An analysis of lower bound procedures for the bin packing problem
    Bourjolly, JM
    Rebetez, V
    COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (03) : 395 - 405
  • [32] Online algorithms with advice for the dual bin packing problem
    Marc P. Renault
    Central European Journal of Operations Research, 2017, 25 : 953 - 966
  • [33] Algorithms for the relaxed online bin-packing model
    Gambosi, G
    Postiglione, A
    Talamo, M
    SIAM JOURNAL ON COMPUTING, 2000, 30 (05) : 1532 - 1551
  • [34] Approximation and online algorithms for multidimensional bin packing: A survey
    Christensen, Henrik I.
    Khan, Arindam
    Pokutta, Sebastian
    Tetali, Prasad
    COMPUTER SCIENCE REVIEW, 2017, 24 : 63 - 79
  • [35] Online algorithms with advice for bin packing and scheduling problems
    Renault, Marc P.
    Rosen, Adi
    van Stee, Rob
    THEORETICAL COMPUTER SCIENCE, 2015, 600 : 155 - 170
  • [36] A CLASS OF SIMPLE STOCHASTIC ONLINE BIN PACKING ALGORITHMS
    HOFFMANN, U
    COMPUTING, 1982, 29 (03) : 227 - 239
  • [37] Online algorithms with advice for the dual bin packing problem
    Renault, Marc P.
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2017, 25 (04) : 953 - 966
  • [38] A lower bound for online rectangle packing
    Leah Epstein
    Journal of Combinatorial Optimization, 2019, 38 : 846 - 866
  • [39] A lower bound for online rectangle packing
    Epstein, Leah
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) : 846 - 866
  • [40] Lower Bounds for Several Online Variants of Bin Packing
    János Balogh
    József Békési
    György Dósa
    Leah Epstein
    Asaf Levin
    Theory of Computing Systems, 2019, 63 : 1757 - 1780
12345