A 3-approximation algorithm for two-dimensional bin packing |
| |
| Authors: | Guochuan Zhang |
| |
| Institution: | a Department of Mathematics, Zhejiang University, China
b Institut für Informatik, Universität Freiburg, Georges-Köhler-Allee 79, 79110 Freiburg, Germany |
| |
| Abstract: | 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. |
| |
| Keywords: | Bin packing Approximation algorithms Absolute worst-case ratio |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
