Dynamic bin packing with unit fraction items revisited

Xin Han; Chao Peng; Deshi Ye; Dahai Zhang; Yan Lan

doi:10.1016/j.ipl.2010.09.002

Dynamic bin packing with unit fraction items revisited

Xin Han^*
, Chao Peng
, Deshi Ye
, Dahai Zhang
, Yan Lan

^*此作品的通讯作者

体育与健康学院

Dalian University of Technology
Zhejiang University
Ocean University of China
Dalian Neusoft University of Information

科研成果: 期刊稿件 › 文章 › 同行评审

12 引用（Scopus）

摘要

In this paper, we will study the problem of dynamic bin packing with unit fraction items. We focus on analyzing the First Fit (FF) algorithm on this problem. There are two main results: i) we give the first bound for the FF algorithm on cases when the largest item is at most 1/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound.

源语言	英语
页（从-至）	1049-1054
页数	6
期刊	Information Processing Letters
卷	110
期	23
DOI	https://doi.org/10.1016/j.ipl.2010.09.002
出版状态	已出版 - 15 11月 2010

访问文件

10.1016/j.ipl.2010.09.002

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{8f5b3e0849b6493d997b418140acd513,

title = "Dynamic bin packing with unit fraction items revisited",

abstract = "In this paper, we will study the problem of dynamic bin packing with unit fraction items. We focus on analyzing the First Fit (FF) algorithm on this problem. There are two main results: i) we give the first bound for the FF algorithm on cases when the largest item is at most 1/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound.",

keywords = "Approximation algorithms, Bin packing problem, Competitive ratio",

author = "Xin Han and Chao Peng and Deshi Ye and Dahai Zhang and Yan Lan",

year = "2010",

month = nov,

day = "15",

doi = "10.1016/j.ipl.2010.09.002",

language = "英语",

volume = "110",

pages = "1049--1054",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "23",

}

TY - JOUR

T1 - Dynamic bin packing with unit fraction items revisited

AU - Han, Xin

AU - Peng, Chao

AU - Ye, Deshi

AU - Zhang, Dahai

AU - Lan, Yan

PY - 2010/11/15

Y1 - 2010/11/15

N2 - In this paper, we will study the problem of dynamic bin packing with unit fraction items. We focus on analyzing the First Fit (FF) algorithm on this problem. There are two main results: i) we give the first bound for the FF algorithm on cases when the largest item is at most 1/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound.

AB - In this paper, we will study the problem of dynamic bin packing with unit fraction items. We focus on analyzing the First Fit (FF) algorithm on this problem. There are two main results: i) we give the first bound for the FF algorithm on cases when the largest item is at most 1/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound.

KW - Approximation algorithms

KW - Bin packing problem

KW - Competitive ratio

UR - https://www.scopus.com/pages/publications/77956597830

U2 - 10.1016/j.ipl.2010.09.002

DO - 10.1016/j.ipl.2010.09.002

M3 - 文章

AN - SCOPUS:77956597830

SN - 0020-0190

VL - 110

SP - 1049

EP - 1054

JO - Information Processing Letters

JF - Information Processing Letters

IS - 23

ER -

Dynamic bin packing with unit fraction items revisited

摘要

访问文件

其它文件与链接

指纹

引用此