×

An approximation scheme for strip packing of rectangles with bounded dimensions. (English) Zbl 0894.68114

Summary: It is shown that for any positive \(\varepsilon\) 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 +\varepsilon\) times the optimal height, in linear time, if the heights and widths of these rectangles are all bounded below by an absolute constant \(\delta>0\).

MSC:

68R99 Discrete mathematics in relation to computer science
05B40 Combinatorial aspects of packing and covering
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Baker, B. S.; Brown, D. J.; Katseff, H. P., A \(54\) algorithm for two-dimensional packing, J. Algorithms, 2, 348-368 (1981) · Zbl 0472.68032
[2] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packings in two dimensions, SIAM J. Comput., 9, 4, 846-855 (1980) · Zbl 0447.68080
[3] Blum, M.; Floyd, R. W.; Pratt, V.; Rivest, R. L.; Tarjan, R. E., Time bounds for selection, J. Comput. System Sci., 7, 448-461 (1973) · Zbl 0278.68033
[4] Coffman, E. G.; Garcy, M. R.; Johnson, D. S.; Tarjan, R. E., Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Comput., 9, 4, 808-826 (1980) · Zbl 0447.68079
[5] de la Vega, W. Fernandez; Lueker, G. S., Bin packing ean be solved within \(1 + ϵ\) in linear time, Combinatorica, 1, 4, 349-355 (1981) · Zbl 0485.68057
[6] Golan, I., Orthogonal oriented algorithms for packing in two dimensions (1978), draft
[7] Johnson, D. S., The NP-completeness column: an ongoing guide, J. Algorithms, 3, 3, 288-300 (1982) · Zbl 0494.68050
[8] Karmarkar, N.; Karp, R. M., An efficient approximation scheme for the one-dimensional bin-packing problem, (22nd Symp. on the Foundations of Computer Science (1982)), 312-320
[9] Kenyon, C.; Rémila, E., (Approximate strip packing, 37th Symp. on the Foundations of Computer Science (1996))
[10] Lenstra, H. W., Integer programming with a fixed number of variable, Math. Oper. Res., 8, 4, 538-548 (1983) · Zbl 0524.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.