𝔖 Bobbio Scriptorium
✦   LIBER   ✦

“A posteriori” evaluation of bin packing approximation algorithms

✍ Scribed by A. Aiello; E. Burattini; A. Massarotti; F. Ventriglia

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
379 KB
Volume
2
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A 1312 approximation algorithm for bin p
A 1312 approximation algorithm for bin packing with extendable bins
✍ Paolo Dell'Olmo; Hans Kellerer; Maria Grazia Speranza; Zsolt Tuza 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 430 KB

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

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.