On-line bin packing — A restricted survey |
| |
Authors: | Gábor Galambos Gerhard J Woeginger |
| |
Institution: | (1) Institut für Mathematik B, TU Graz, Kopernikusgasse 24, 8010 Graz, Austria;(2) Institut für Theoretische Informatik, TU Graz, Klosterwiesgasse 32/II, 8010 Graz, Austria |
| |
Abstract: | In the classical bin packing problem, one is asked to pack items of various sizes into the minimum number of equal-sized bins. In the on-line version of this problem, the packer is given the items one by one and must immediately and irrevocably assign every item to its bin, without knowing the future items. Beginning with the first results in the early 1970's, we survey — from the worst case point of view — the approximation results obtained for on-line bin packing, higher dimensional versions of the problem, lower bounds on worst case ratios and related results.This work was partially supported by the Christian Doppier Laboratorium für Diskrete Optimierung. |
| |
Keywords: | combinatorial problems on-line bin packing approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|