Abstract
We propose and motivate a new variant of the wellknown two-dimensional binpacking problem (orthogonal and oriented rectangle packing). In our model, we are allowed to cut a rectangle and move the parts horizontally. We describe two relatively simple algorithms for this problem and determine their asymptotic performance ratios. For the best algorithm, we show that this ratio is between 1.302... and 4/3.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, B.S., Brown, D.J. and Katseff, H.P., A 5/4 algorithm for two-dimensional packing, J. of Algorithms, 2 (1981), p. 348–368.
Baker, B.S. and Coffman Jr., E.G., A tight asymptotic bound for next-fit-decreasing binpacking, SIAM J. Alg. Disc. Meth., 2 (1981), p. 147–152.
Baker, B.S., Coffman Jr., E.G. and Rivest, R.L., Orthogonal packings in two dimensions, SIAM J. Comput., 4 (1980), p. 846–855.
Baker, B.S. and Schwarz, J.S., Shelf algorithms for two-dimensional packing problems, SIAM J. Comput., 3 (1983), p. 508–525.
Coffman Jr., E.G., Garey, M.R. and Johnsen, D.S., Approximation algorithms for bin-packing — An updated survey, Technical report, AT&T Bell Laboratories, Murray Hill, New Jersey.
Coffman Jr., E.G., Garey, M.R., Johnsen, D.S. and Tarjan, R.E., Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Comput., 4 (1981), p. 808–826.
Høyland, S.O., Kuttepakking — Ein ny pakkemodell, Hovudoppgåve i informatikk, Dept. of Informatics, University of Bergen (1985) (in Norwegian).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Høyland, SO. (1988). Bin-packing in 1.5 dimension. In: Karlsson, R., Lingas, A. (eds) SWAT 88. SWAT 1988. Lecture Notes in Computer Science, vol 318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-19487-8_14
Download citation
DOI: https://doi.org/10.1007/3-540-19487-8_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-19487-3
Online ISBN: 978-3-540-39288-0
eBook Packages: Springer Book Archive