|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
Online bin packing with (1,1) and (2,) bins
点击次数：
论文类型：期刊论文
发表时间：2015-08-01
发表刊物：JOURNAL OF COMBINATORIAL OPTIMIZATION
收录刊物：SCIE、EI、Scopus
卷号：30
期号：2,SI
页面范围：276-298
ISSN号：1382-6905
关键字：Bin packing; Competitive ratio; Linear programming
摘要：We study a variant of online bin packing problem, in which there are two types of bins: and , i.e., unit size bin with cost 1 and size 2 bin with cost , the objective is to minimize the total cost occurred when all the items are packed into the two types of bins. When , the offline version of this problem is equivalent to the classical bin packing problem. In this paper, we focus on the case , and propose online algorithms and obtain lower bounds for the problem.