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

^*Corresponding author for this work

College of Physical Education and Health

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

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

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.

Original language	English
Pages (from-to)	1049-1054
Number of pages	6
Journal	Information Processing Letters
Volume	110
Issue number	23
DOIs	https://doi.org/10.1016/j.ipl.2010.09.002
State	Published - 15 Nov 2010

Keywords

Approximation algorithms
Bin packing problem
Competitive ratio

Access to Document

10.1016/j.ipl.2010.09.002

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this