Skip to main content
SpringerLink
Log in

Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width

  • Conference paper
  • First Online:
WALCOM: Algorithms and Computation (WALCOM 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10167))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Adamaszek, A., Kociumaka, T., Pilipczuk, M., Pilipczuk, M.: Hardness of approximation for strip packing. CoRR abs/1610.07766 (2016)

    Google Scholar 

  2. Baker, B., Brown, D., Katseff, H.: A \(5/4\) algorithm for two-dimensional packing. J. Algorithms 2(4), 348–368 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  3. Baker, B., Coffman Jr., E.G., Rivest, R.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846–855 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  4. 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)

    Article  MathSciNet  MATH  Google Scholar 

  5. 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)

    Google Scholar 

  6. Golan, I.: Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM J. Comput. 10(3), 571–582 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  7. 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)

    Article  MathSciNet  MATH  Google Scholar 

  8. 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

    Chapter  Google Scholar 

  9. Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. CoRR abs/1610.04430 (2016)

    Google Scholar 

  10. Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discrete Optim. 6(3), 310–323 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Jansen, K., Thöle, R.: Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8), 3571–3615 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Kenyon, C., Rémila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645–656 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  13. 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)

    Google Scholar 

  14. 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

    Chapter  Google Scholar 

  15. Sleator, D.: A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett. 10(1), 37–40 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  16. Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401–409 (1997)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computer Science, University of Kiel, 24118, Kiel, Germany

    Klaus Jansen & Malin Rau

Authors
  1. Klaus Jansen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Malin Rau
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Malin Rau .

Editor information

Editors and Affiliations

  1. Universiti Teknologi Brunei, Bandar Seri Begawan, Brunei Darussalam

    Sheung-Hung Poon

  2. Bangladesh University of Engineering and Technology, Dhaka, Bangladesh

    Md. Saidur Rahman

  3. National Taiwan University, Taipei, Taiwan

    Hsu-Chun Yen

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics

Search

Navigation