Abstract
We study the well-known two-dimensional strip packing problem. Given is a set of rectangular axis-parallel items and a strip of width W with infinite height. The objective is to find a packing of these items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of 3/2 of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type \((n W)^{f(1/\varepsilon )}\), for any function f. If W is polynomially bounded by the number of items, this is a polynomial running-time. We present a pseudo-polynomial algorithm with approximation ratio \(4/3 +\varepsilon \) and running time \((n W)^{1/\varepsilon ^{\mathcal {O}(2^{1/\varepsilon })}}\).
Research was supported by German Research Foundation (DFG) project JA 612/14-2.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adamaszek, A., Kociumaka, T., Pilipczuk, M., Pilipczuk, M.: Hardness of approximation for strip packing. CoRR abs/1610.07766 (2016)
Baker, B., Brown, D., Katseff, H.: A \(5/4\) algorithm for two-dimensional packing. J. Algorithms 2(4), 348–368 (1981)
Baker, B., Coffman Jr., E.G., Rivest, R.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846–855 (1980)
Coffman Jr., E., Garey, M., Johnson, D., Tarjan, R.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4), 808–826 (1980)
Gálvez, W., Grandoni, F., Ingala, S., Khan, A.: Improved pseudo-polynomial-time approximation for strip packing. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, 13–15 December 2016, Chennai, India, pp. 9:1–9:14 (2016)
Golan, I.: Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM J. Comput. 10(3), 571–582 (1981)
Harren, R., Jansen, K., Prädel, L., Van Stee, R.: A (\(5/3+\varepsilon \))-approximation for strip packing. Comput. Geom. 47(2), 248–267 (2014)
Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX/RANDOM 2009. LNCS, vol. 5687, pp. 177–189. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03685-9_14
Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. CoRR abs/1610.04430 (2016)
Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discrete Optim. 6(3), 310–323 (2009)
Jansen, K., Thöle, R.: Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8), 3571–3615 (2010)
Kenyon, C., Rémila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645–656 (2000)
Nadiradze, G., Wiese, A.: On approximating strip packing with a better ratio than 3/2. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491–1510. SIAM (2016)
Schiermeyer, I.: Reverse-fit: a 2-optimal algorithm for packing rectangles. In: Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 290–299. Springer, Heidelberg (1994). doi:10.1007/BFb0049416
Sleator, D.: A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett. 10(1), 37–40 (1980)
Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401–409 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jansen, K., Rau, M. (2017). Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width. In: Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation. WALCOM 2017. Lecture Notes in Computer Science(), vol 10167. Springer, Cham. https://doi.org/10.1007/978-3-319-53925-6_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-53925-6_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53924-9
Online ISBN: 978-3-319-53925-6
eBook Packages: Computer ScienceComputer Science (R0)