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 条
  • [41] Lower Bounds for Several Online Variants of Bin Packing
    Balogh, Janos
    Bekesi, Jozsef
    Dosa, Gyoergy
    Epstein, Leah
    Levin, Asaf
    THEORY OF COMPUTING SYSTEMS, 2019, 63 (08) : 1757 - 1780
  • [42] Improved approximation algorithms for multidimensional bin packing problems
    Bansal, Nikhil
    Caprara, Alberto
    Sviridenko, Maxim
    47TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2006, : 697 - +
  • [43] Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing
    Zhang, Yong
    Chen, Jingchi
    Chin, Francis Y. L.
    Han, Xin
    Ting, Hing-Fung
    Tsin, Yung H.
    ALGORITHMS AND COMPUTATION, PT 2, 2010, 6507 : 242 - +
  • [44] Online LIB problems: Heuristics for bin covering and lower bounds for bin packing
    Finlay, L
    Manyem, P
    RAIRO-OPERATIONS RESEARCH, 2005, 39 (03) : 163 - 183
  • [45] Improved Online Algorithms for 2-Space Bounded 2-Dimensional Bin Packing
    Januszewski, Janusz
    Zielonka, Lukasz
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2016, 27 (04) : 407 - 429
  • [46] A new lower bound on the price of anarchy of selfish bin packing
    Dosa, Gyorgy
    Epstein, Leah
    INFORMATION PROCESSING LETTERS, 2019, 150 : 6 - 12
  • [47] Online algorithms for 2D bin packing with advice
    Zhao, Xiaofan
    Shen, Hong
    NEUROCOMPUTING, 2016, 189 : 25 - 32
  • [48] New Lower Bounds for Certain Classes of Bin Packing Algorithms
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    APPROXIMATION AND ONLINE ALGORITHMS, 2011, 6534 : 25 - 36
  • [49] New lower bounds for certain classes of bin packing algorithms
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    THEORETICAL COMPUTER SCIENCE, 2012, 440 : 1 - 13
  • [50] A new lower bound for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 250 (03) : 754 - 759
12345