Document Open Access Logo

A Tight (3/2+ε) Approximation for Skewed Strip Packing

Authors Waldo Gálvez , Fabrizio Grandoni , Afrouz Jabal Ameli , Klaus Jansen , Arindam Khan , Malin Rau

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.44.pdf
  • Filesize: 0.56 MB
  • 18 pages

Document Identifiers

Author Details

Waldo Gálvez
  • Technical University of Munich, Germany
Fabrizio Grandoni
  • IDSIA, USI-SUPSI, Manno, Switzerland
Afrouz Jabal Ameli
  • IDSIA, USI-SUPSI, Manno, Switzerland
Klaus Jansen
  • University of Kiel, Germany
Arindam Khan
  • Indian Institute of Science, Bangalore, India
Malin Rau
  • Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP*, LIG, Grenoble, France

Funding

  • Grandoni, Fabrizio: Partially supported by the SNSF Excellence Grant 200020B_182865/1.
  • Ameli, Afrouz Jabal: Partially supported by the SNSF Excellence Grant 200020B_182865/1.
  • Rau, Malin: Partially supported by the French research program ENERGUMEN ANR-18-CE25-0008.

Cite As Get BibTex

Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A Tight (3/2+ε) Approximation for Skewed Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.44

Abstract

In the Strip Packing problem, we are given a vertical half-strip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NP-hard to approximate this problem within a factor (3/2-ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis.
It seems plausible that Strip Packing admits a (3/2+ε)-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor (3/2-ε) and we provide an (almost) tight (3/2+ε)-approximation algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • strip packing
  • approximation algorithm

Metrics

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

References

  1. Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. Hardness of approximation for strip packing. ACM Transactions on Computation Theory, 9(3):14:1-14:7, 2017. URL: https://doi.org/10.1145/3092026.
  2. Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 400-409. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.50.
  3. Anna Adamaszek and Andreas Wiese. A quasi-ptas for the two-dimensional geometric knapsack problem. In Piotr Indyk, editor, 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. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.98.
  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, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko. A structural lemma in 2-dimensional packing, and its implications on approximability. In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors, Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878 of Lecture Notes in Computer Science, pages 77-86. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-10631-6_10.
  6. Nikhil Bansal, José R. Correa, Claire Kenyon, and Maxim Sviridenko. Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Mathematics of Operations Research, 31(1):31-49, 2006. URL: https://doi.org/10.1287/moor.1050.0168.
  7. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 13-25. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  8. Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 892-901. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496867.
  9. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. URL: https://doi.org/10.1007/s00454-012-9417-5.
  10. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63-79, 2017. URL: https://doi.org/10.1016/j.cosrev.2016.12.001.
  11. Edward Grady Coffman and John L. Bruno. Computer and job-shop scheduling theory. Wiley New York, 1976. Google Scholar
  12. Edward G. Coffman Jr., János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin Packing Approximation Algorithms: Survey and Classification, pages 455-531. Springer New York, New York, NY, 2013. URL: https://doi.org/10.1007/978-1-4419-7997-1_35.
  13. Leah Epstein and Rob van Stee. This side up! ACM Transactions on Algorithms, 2(2):228-243, 2006. URL: https://doi.org/10.1145/1150334.1150339.
  14. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 260-271. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.32.
  15. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. CoRR, abs/1711.07710, 2017. URL: http://arxiv.org/abs/1711.07710.
  16. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. Improved pseudo-polynomial-time approximation for strip packing. In Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen, editors, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, volume 65 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9.
  17. M. R. Garey and David S. Johnson. "strong" np-completeness results: Motivation, examples, and implications. Journal of the ACM, 25(3):499-508, 1978. URL: https://doi.org/10.1145/322077.322090.
  18. 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.
  19. Rolf Harren and Rob van Stee. Improved absolute approximation ratios for two-dimensional packing problems. In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, 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.
  20. Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje. Complexity and inapproximability results for parallel task scheduling and strip packing. Theory of Computing Systems, 64(1):120-140, 2020. URL: https://doi.org/10.1007/s00224-019-09910-6.
  21. Klaus Jansen and Lars Prädel. A new asymptotic approximation algorithm for 3-dimensional strip packing. In Viliam Geffert, Bart Preneel, Branislav Rovan, Julius Stuller, and A Min Tjoa, editors, SOFSEM 2014: Theory and Practice of Computer Science - 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings, volume 8327 of Lecture Notes in Computer Science, pages 327-338. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-04298-5_29.
  22. Klaus Jansen and Malin Rau. Closing the gap for pseudo-polynomial strip packing. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 62:1-62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.62.
  23. Klaus Jansen and Malin Rau. Improved approximation for two dimensional strip packing with polynomial bounded width. Theoretical Computer Science, 789:34-49, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.002.
  24. Klaus Jansen and Roberto Solis-Oba. New approximability results for 2-dimensional packing problems. In Ludek Kucera and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pages 103-114. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74456-6_11.
  25. Klaus Jansen and Rob van Stee. On strip packing with rotations. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 755-761. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060702.
  26. Klaus Jansen and Guochuan Zhang. Maximizing the total profit of rectangles packed into a rectangle. Algorithmica, 47(3):323-342, 2007. URL: https://doi.org/10.1007/s00453-006-0194-5.
  27. Edward G. Coffman Jr., M. 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.
  28. Mohammad M. Karbasioun, Gennady Shaikhet, Evangelos Kranakis, and Ioannis Lambadaris. Power strip packing of malleable demands in smart grid. In Proceedings of IEEE International Conference on Communications, ICC 2013, Budapest, Hungary, June 9-13, 2013, pages 4261-4265. IEEE, 2013. URL: https://doi.org/10.1109/ICC.2013.6655233.
  29. 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.
  30. Arindam Khan. Approximation algorithms for multidimensional bin packing. PhD thesis, Georgia Institute of Technology, Atlanta, GA, USA, 2016. URL: http://hdl.handle.net/1853/54371.
  31. Joseph Y.-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin. Packing squares into a square. Journal on Parallel and Distributed Computing, 10(3):271-275, 1990. URL: https://doi.org/10.1016/0743-7315(90)90019-L.
  32. Flávio Keidi Miyazawa and Yoshiko Wakabayashi. Packing problems with orthogonal rotations. In Martin Farach-Colton, editor, LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings, volume 2976 of Lecture Notes in Computer Science, pages 359-368. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24698-5_40.
  33. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1491-1510. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch102.
  34. Ingo Schiermeyer. Reverse-fit: A 2-optimal algorithm for packing rectangles. In Jan van Leeuwen, editor, Algorithms - ESA '94, Second Annual European Symposium, Utrecht, The Netherlands, September 26-28, 1994, Proceedings, volume 855 of Lecture Notes in Computer Science, pages 290-299. Springer, 1994. URL: https://doi.org/10.1007/BFb0049416.
  35. 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.
  36. 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.
  37. Shaojie Tang, Qiuyuan Huang, Xiang-Yang Li, and Dapeng Wu. Smoothing the energy consumption: Peak demand reduction in smart grid. In Proceedings of the IEEE INFOCOM 2013, Turin, Italy, April 14-19, 2013, pages 1133-1141. IEEE, 2013. URL: https://doi.org/10.1109/INFCOM.2013.6566904.
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