Indexed by:期刊论文

Date of Publication:2010-11-15

Journal:INFORMATION PROCESSING LETTERS

Included Journals:SCIE、EI、Scopus

Volume:110

Issue:23

Page Number:1049-1054

ISSN No.:0020-0190

Key Words:Approximation algorithms; Competitive ratio; Bin packing problem

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. (C) 2010 Elsevier B.V. All rights reserved.