AN APPROXIMATION SCHEME FOR STRIP PACKING OF RECTANGLES WITH BOUNDED DIMENSIONS

Authors
DELAVEGA WF ZISSIMOPOULOS V
Citation
Wf. Delavega et V. Zissimopoulos, AN APPROXIMATION SCHEME FOR STRIP PACKING OF RECTANGLES WITH BOUNDED DIMENSIONS, Discrete applied mathematics, 82(1-3), 1998, pp. 93-101
Citations number
10
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
82
Issue
1-3
Year of publication
1998
Pages
93 - 101
Database
ISI
SICI code
Abstract
It is shown that for any positive epsilon the strip-packing problem, i .e. the problem of packing a given list of rectangles into a strip of width 1 and minimum height, can be solved within 1 + epsilon times the optimal height, in linear time, if the heights and widths of these re ctangles are all bounded below by an absolute constant delta > 0. (C) 1998 Elsevier Science B.V. All rights reserved.