Document Open Access Logo

Improved Pseudo-Polynomial-Time Approximation for Strip Packing

Authors Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Arindam Khan

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.9.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Waldo Gálvez
Fabrizio Grandoni
Salvatore Ingala
Arindam Khan

Cite As Get BibTex

Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. Improved Pseudo-Polynomial-Time Approximation for Strip Packing. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9

Abstract

We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated.

A reduction from the partition problem shows that no approximation better than 3/2 is possible for strip packing in polynomial time (assuming P!=NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a (7/5+epsilon)-approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm (though a PPT approximation scheme might exist).

In this paper we make further progress on the PPT approximability of strip packing, by presenting a (4/3+epsilon)-approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the "empty space" left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. 

Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by 90 degrees, achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3/2 for the case with rotations as well.

Subject Classification

Keywords
  • approximation algorithms
  • strip packing
  • rectangle packing
  • cutting-stock problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In FOCS, pages 400-409, 2013. Google Scholar
  2. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the two-dimensional geometric knapsack problem. In SODA, pages 1491-1505, 2015. Google Scholar
  3. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. Constant integrality gap LP formulations of unsplittable flow on a path. In IPCO, pages 25-36, 2013. Google Scholar
  4. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+ε approximation for unsplittable flow on a path. In SODA, pages 26-41, 2014. Google Scholar
  5. Brenda S. Baker, Donna J. Brown, and Howard P. Katseff. A 5/4 algorithm for two-dimensional packing. Journal of algorithms, 2(4):348-368, 1981. Google Scholar
  6. Brenda S. Baker, Edward G. Coffman Jr., and Ronald L. Rivest. Orthogonal packings in two dimensions. SIAM J. Comput., 9(4):846-855, 1980. Google Scholar
  7. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, and Baruch Schieber. A quasi-PTAS for unsplittable flow on line graphs. In STOC, pages 721-729, 2006. Google Scholar
  8. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In SODA, pages 13-25, 2014. Google Scholar
  9. Paul S. Bonsma, Jens Schulz, and Andreas Wiese. A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Comput., 43(2):767-799, 2014. Google Scholar
  10. Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In SODA, pages 892-901, 2009. Google Scholar
  11. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. Google Scholar
  12. Edward G. Coffman Jr. and John L. Bruno. Computer and job-shop scheduling theory. John Wiley &Sons, 1976. Google Scholar
  13. Edward G. Coffman Jr., János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: survey and classification. In Handbook of Combinatorial Optimization, pages 455-531. Springer, 2013. Google Scholar
  14. Edward G. Coffman Jr., Michael R. Garey, David S. Johnson, and Robert E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808-826, 1980. Google Scholar
  15. Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1+ ε in linear time. Combinatorica, 1(4):349-355, 1981. Google Scholar
  16. Leah Epstein and Rob van Stee. This side up! ACM Transactions on Algorithms (TALG), 2(2):228-243, 2006. Google Scholar
  17. Michael R. Garey and David S. Johnson. "Strong" NP-completeness results: Motivation, examples, and implications. JACM, 25(3):499-508, 1978. Google Scholar
  18. Igal Golan. Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM Journal on Computing, 10(3):571-582, 1981. Google Scholar
  19. Fabrizio Grandoni, Salvatore Ingala, and Sumedha Uniyal. Improved approximation algorithms for unsplittable flow on a path with time windows. In WAOA, pages 13-24, 2015. Google Scholar
  20. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee. A (5/3+ ε)-approximation for strip packing. Computational Geometry, 47(2):248-267, 2014. Google Scholar
  21. Rolf Harren and Rob van Stee. Improved absolute approximation ratios for two-dimensional packing problems. In APPROX-RANDOM, pages 177-189. Springer, 2009. Google Scholar
  22. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences, 79(1):39-49, 2013. Google Scholar
  23. Klaus Jansen and Lars Prädel. A new asymptotic approximation algorithm for 3-dimensional strip packing. In SOFSEM, pages 327-338, 2014. Google Scholar
  24. Klaus Jansen and Roberto Solis-Oba. Rectangle packing with one-dimensional resource augmentation. Discrete Optimization, 6(3):310-323, 2009. Google Scholar
  25. Klaus Jansen and Rob van Stee. On strip packing with rotations. In STOC, pages 755-761, 2005. Google Scholar
  26. Klaus Jansen and Guochuan Zhang. Maximizing the total profit of rectangles packed into a rectangle. Algorithmica, 47(3):323-342, 2007. Google Scholar
  27. Mohammad M. Karbasioun, Gennady Shaikhet, Evangelos Kranakis, and Ioannis Lambadaris. Power strip packing of malleable demands in smart grid. In IEEE International Conference on Communications, pages 4261-4265, 2013. Google Scholar
  28. Claire Kenyon and Eric Rémila. A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res., 25(4):645-656, 2000. Google Scholar
  29. Arindam Khan. Approximation Algorithms for Multidimensional Bin Packing. PhD thesis, Georgia Institute of Technology, USA, 2015. Google Scholar
  30. Flavio Keidi Miyazawa and Yoshiko Wakabayashi. Packing problems with orthogonal rotations. In LATIN, pages 359-368. Springer, 2004. Google Scholar
  31. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing better than 3/2. In SODA, pages 1491-1510, 2016. Google Scholar
  32. Anshu Ranjan, Pramod Khargonekar, and Sartaj Sahni. Offline first fit scheduling in smart grids. In IEEE SCC, pages 758-763, 2015. Google Scholar
  33. Ingo Schiermeyer. Reverse-fit: A 2-optimal algorithm for packing rectangles. In Algorithms—ESA'94, pages 290-299. Springer, 1994. Google Scholar
  34. Daniel Sleator. A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Letters, 10(1):37-40, 1980. Google Scholar
  35. A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing, 26(2):401-409, 1997. Google Scholar
  36. Shaojie Tang, Qiuyuan Huang, Xiang-Yang Li, and Dapeng Wu. Smoothing the energy consumption: Peak demand reduction in smart grid. In INFOCOM, pages 1133-1141. IEEE, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact