Document Open Access Logo

Closing the Gap for Pseudo-Polynomial Strip Packing

Authors Klaus Jansen, Malin Rau

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.62.pdf
  • Filesize: 453 kB
  • 14 pages

Document Identifiers

Author Details

Klaus Jansen
  • Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Germany
Malin Rau
  • L'Institute Polytechnique de Grenoble, Grenoble INP, France

Funding

Research was supported by German Research Foundation (DFG) project JA 612 /20-1.

Cite As Get BibTex

Klaus Jansen and Malin Rau. Closing the Gap for Pseudo-Polynomial Strip Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.62

Abstract

Two-dimensional packing problems are a fundamental class of optimization problems and Strip Packing is one of the most natural and famous among them. Indeed it can be defined in just one sentence: Given a set of rectangular axis parallel items and a strip with bounded width and infinite height, the objective is to find a packing of the items into the strip minimizing the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip. It is known that there is no pseudo-polynomial time algorithm for Strip Packing with a ratio better than 5/4 unless P = NP. The best algorithm so far has a ratio of 4/3 + epsilon. In this paper, we close the gap between inapproximability result and currently known algorithms by presenting an algorithm with approximation ratio 5/4 + epsilon. The algorithm relies on a new structural result which is the main accomplishment of this paper. It states that each optimal solution can be transformed with bounded loss in the objective such that it has one of a polynomial number of different forms thus making the problem tractable by standard techniques, i.e., dynamic programming. To show the conceptual strength of the approach, we extend our result to other problems as well, e.g., Strip Packing with 90 degree rotations and Contiguous Moldable Task Scheduling, and present algorithms with approximation ratio 5/4 + epsilon for these problems as well.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Scheduling algorithms
Keywords
  • Strip Packing
  • pseudo-polynomial
  • 90 degree rotation
  • Contiguous Moldable Task Scheduling

Metrics

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

Related Versions

References

  1. Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. Hardness of Approximation for Strip Packing. TOCT, 9(3):14:1-14:7, 2017. URL: https://doi.org/10.1145/3092026.
  2. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1491-1505, 2015. URL: https://doi.org/10.1137/1.9781611973730.98.
  3. 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. URL: https://doi.org/10.1016/0196-6774(81)90034-1.
  4. Brenda S. Baker, Edward G. Coffman Jr., and Ronald L. Rivest. Orthogonal Packings in Two Dimensions. SIAM Journal on Computing, 9(4):846-855, 1980. URL: https://doi.org/10.1137/0209064.
  5. Nikhil Bansal and Arindam Khan. Improved Approximation Algorithm for Two-Dimensional Bin Packing. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 13-25, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  6. Marin Bougeret, Pierre-François Dutot, Klaus Jansen, Christina Robenek, and Denis Trystram. Approximation Algorithms for Multiple Strip Packing and Scheduling Parallel Jobs in Platforms. Discrete Mathematics, Algorithms and Applications, 3(4):553-586, 2011. URL: https://doi.org/10.1142/S1793830911001413.
  7. Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optimality of approximation schemes for the classical scheduling problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 657-668, 2014. URL: https://doi.org/10.1137/1.9781611973402.50.
  8. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 2017. URL: https://doi.org/10.1016/j.cosrev.2016.12.001.
  9. Edward G. Coffman Jr., Michael R. Garey, David S. Johnson, and Robert Endre Tarjan. Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM Journal on Computing, 9(4):808-826, 1980. URL: https://doi.org/10.1137/0209062.
  10. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating Geometric Knapsack via L-Packings. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 260-271, 2017. URL: https://doi.org/10.1109/FOCS.2017.32.
  11. 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), pages 9:1-9:14, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9.
  12. Igal Golan. Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms. SIAM Journal on Computing, 10(3):571-582, 1981. URL: https://doi.org/10.1137/0210042.
  13. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2411-2422, 2017. URL: https://doi.org/10.1137/1.9781611974782.159.
  14. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 607-619, 2018. URL: https://doi.org/10.1145/3188745.3188894.
  15. 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. URL: https://doi.org/10.1016/j.comgeo.2013.08.008.
  16. Rolf Harren and Rob van Stee. Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,, volume 5687 of Lecture Notes in Computer Science, pages 177-189. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_14.
  17. Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje. Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. In Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings, pages 169-180, 2018. URL: https://doi.org/10.1007/978-3-319-90530-3_15.
  18. Sandy Heydrich and Andreas Wiese. Faster approximation schemes for the two-dimensional knapsack problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 79-98, 2017. URL: https://doi.org/10.1137/1.9781611974782.6.
  19. Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the Gap for Makespan Scheduling via Sparsification Techniques. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 72:1-72:13, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.72.
  20. Klaus Jansen and Felix Land. Scheduling Monotone Moldable Jobs in Linear Time. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pages 172-181, 2018. URL: https://doi.org/10.1109/IPDPS.2018.00027.
  21. Klaus Jansen and Malin Rau. Improved approximation for two dimensional strip packing with polynomial bounded width. In WALCOM: Algorithms and Computation, volume 10167 of LNCS, pages 409-420, 2017. URL: https://doi.org/10.1007/978-3-319-53925-6_32.
  22. Klaus Jansen and Roberto Solis-Oba. Rectangle packing with one-dimensional resource augmentation. Discrete Optimization, 6(3):310-323, 2009. URL: https://doi.org/10.1016/j.disopt.2009.04.001.
  23. Klaus Jansen and Ralf Thöle. Approximation Algorithms for Scheduling Parallel Jobs. SIAM Journal on Computing, 39(8):3571-3615, 2010. URL: https://doi.org/10.1137/080736491.
  24. Claire Kenyon and Eric Rémila. A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem. Mathematics of Operations Research, 25(4):645-656, 2000. URL: https://doi.org/10.1287/moor.25.4.645.12118.
  25. Walter Ludwig and Prasoon Tiwari. Scheduling Malleable and Nonmalleable Parallel Tasks. In 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 167-176, 1994. Google Scholar
  26. Gregory Mounie, Christophe Rapine, and Denis Trystram. A 3/2-Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks. SIAM J. Comput., 37(2):401-412, 2007. URL: https://doi.org/10.1137/S0097539701385995.
  27. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1491-1510, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch102.
  28. Ingo Schiermeyer. Reverse-Fit: A 2-Optimal Algorithm for Packing Rectangles. In 2nd Annual European Symposium on Algorithms (ESA) - Algorithms, pages 290-299, 1994. URL: https://doi.org/10.1007/BFb0049416.
  29. Daniel Dominic Sleator. A 2.5 Times Optimal Algorithm for Packing in Two Dimensions. Information Processing Letters, 10(1):37-40, 1980. URL: https://doi.org/10.1016/0020-0190(80)90121-0.
  30. A. Steinberg. A Strip-Packing Algorithm with Absolute Performance Bound 2. SIAM Journal on Computing, 26(2):401-409, 1997. URL: https://doi.org/10.1137/S0097539793255801.
  31. Maxim Sviridenko. A note on the Kenyon-Remila strip-packing algorithm. Information Processing Letters, 112(1-2):10-12, 2012. URL: https://doi.org/10.1016/j.ipl.2011.10.003.
  32. John Turek, Joel L. Wolf, and Philip S. Yu. Approximate Algorithms Scheduling Parallelizable Tasks. In 4th annual ACM symposium on Parallel algorithms and architectures (SPAA), pages 323-332, 1992. URL: https://doi.org/10.1145/140901.141909.
  33. Andreas Wiese. A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 67:1-67:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.67.
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