Lower Bounds for Several Online Variants of Bin Packing

被引：0
作者：
János Balogh
József Békési
György Dósa
Leah Epstein
Asaf Levin
机构：
[1] University of Szeged,Department of Applied Informatics, Gyula Juhász Faculty of Education
[2] University of Pannonia,Department of Mathematics
[3] University of Haifa,Department of Mathematics
[4] Faculty of Industrial Engineering and Management,undefined
[5] The Technion,undefined
来源：
Theory of Computing Systems | 2019年 / 63卷
关键词：
Bin packing; Online algorithms; Lower bounds; Competitive ratio;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75.
引用
收藏
页码：1757 / 1780
页数：23
相关论文
共 60 条
[1]  
Babel L(2004)Algorithms for on-line bin-packing problems with cardinality constraints Discret. Appl. Math. 143 238-251
[2]  
Chen B(2013)Semi-on-line bin packing: a short overview and a new lower bound CEJOR 21 685-698
[3]  
Kellerer H(2012)New lower bounds for certain classes of bin packing algorithms Theor. Comput. Sci. 440-441 1-13
[4]  
Kotov V(2006)Bin packing in multiple dimensions Inapproximability results and approximation schemes Math. Oper. Res. 31 31-49
[5]  
Balogh J(2016)Bounds for online bin packing with cardinality constraints Inf. Comput. 249 190-204
[6]  
Békési J(2016)Online bin packing with advice Algorithmica 74 507-527
[7]  
Balogh J(1989)Multidimensional online bin packing: Algorithms and worst case analysis Oper. Res. Lett. 8 17-20
[8]  
Békési J(2006)Online bin packing with cardinality constraints SIAM J. Discret. Math. 20 1015-1030
[9]  
Galambos G(2010)Class constrained bin packing revisited Theor. Comput. Sci. 411 3073-3089
[10]  
Bansal N(2008)On bin packing with conflicts SIAM J. Optim. 19 1270-1298
123456