A 13 12 APPROXIMATION ALGORITHM FOR BIN PACKING WITH EXTENDIBLE BINS/

Authors
DELLOLMO P KELLERER H SPERANZA MG TUZA Z
Citation
P. Dellolmo et al., A 13 12 APPROXIMATION ALGORITHM FOR BIN PACKING WITH EXTENDIBLE BINS/, Information processing letters, 65(5), 1998, pp. 229-233
Citations number
4
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
65
Issue
5
Year of publication
1998
Pages
229 - 233
Database
ISI
SICI code
0020-0190(1998)65:5<229:A11AAF>2.0.ZU;2-F
Abstract
A set of items has to be assigned to a set of bins with size one. If n ecessary, the size of the bins can be extended. The objective is to mi nimize the total size, i.e., the sum of the sizes of the bins. The Lon gest Processing Time heuristic is applied to this NP-hard problem. For this approximation algorithm we prove a worst-case bound of 13/12 whi ch is shown to be tight when the number of bins is even. (C) 1998 Else vier Science B.V.