𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A 1312 approximation algorithm for bin packing with extendable bins

✍ Scribed by Paolo Dell'Olmo; Hans Kellerer; Maria Grazia Speranza; Zsolt Tuza

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
430 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

A set of items has to be assigned to a set of bins with size one. If necessary, the size of the bins can be extended. The objective is to minimize the total size, i.e., the sum of the sizes of the bins. The Longest Processing Time heuristic is applied to this NP-hard problem. For this approximation algorithm we prove a worst-case bound of 13/12 which is shown to be tight when the number of bins is even. @

πŸ“œ SIMILAR VOLUMES

A 3-approximation algorithm for two-dime
A 3-approximation algorithm for two-dimensional bin packing
✍ Guochuan Zhang πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 189 KB

In the classical two-dimensional bin packing problem one is asked to pack a set of rectangular items, without overlap and without any rotation, into the minimum number of identical square bins. We give an approximation algorithm with absolute worst-case ratio of 3.