Document Open Access Logo

Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items

Authors Arindam Khan, Eklavya Sharma

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.22.pdf
  • Filesize: 0.84 MB
  • 23 pages

Document Identifiers

Author Details

Arindam Khan
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Eklavya Sharma
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Cite As Get BibTex

Arindam Khan and Eklavya Sharma. Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.22

Abstract

In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillotine Two-dimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let λ be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by λ opt(I) + c, where opt(I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4/3 ≤ λ ≤ 1.692. Bansal and Khan [SODA'14] conjectured that λ = 4/3. The conjecture, if true, will imply a (4/3+ε)-approximation algorithm for 2BP. According to convention, for a given constant δ > 0, a rectangle is large if both its height and width are at least δ, and otherwise it is called skewed. We make progress towards the conjecture by showing λ = 4/3 for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on λ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Geometric bin packing
  • guillotine separability
  • approximation algorithms

Metrics

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

Related Versions

References

  1. Fidaa Abed, Parinya Chalermsook, José Correa, Andreas Karrenbauer, Pablo Pérez-Lantero, José A Soto, and Andreas Wiese. On guillotine cutting sequences. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 1-19, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.1.
  2. Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independent set and sparse subsets of polygons. Journal of the ACM, 66(4):29:1-29:40, 2019. URL: https://doi.org/10.1145/3326122.
  3. Soroush Alamdari, Therese Biedl, Timothy M Chan, Elyot Grant, Krishnam Raju Jampani, Srinivasan Keshav, Anna Lubiw, and Vinayak Pathak. Smart-grid electricity allocation via strip packing with slicing. In Workshop on Algorithms and Data Structures (WADS), pages 25-36. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_3.
  4. Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4):1256-1278, 2010. URL: https://doi.org/10.1137/080736831.
  5. 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.
  6. Nikhil Bansal, Marek Eliáš, and Arindam Khan. Improved approximation for vector bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1561-1579. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch106.
  7. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 13-25, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  8. Nikhil Bansal, Andrea Lodi, and Maxim Sviridenko. A tale of two dimensional bin packing. In Symposium on Foundations of Computer Science (FOCS), pages 657-666. IEEE, 2005. URL: https://doi.org/10.1109/SFCS.2005.10.
  9. Alberto Caprara. Packing d-dimensional bins in d stages. Mathematics of Operations Research, 33:203-215, February 2008. URL: https://doi.org/10.1287/moor.1070.0289.
  10. Alberto Caprara, Andrea Lodi, and Michele Monaci. Fast approximation schemes for two-stage, two-dimensional bin packing. Mathematics of Operations Research, 30(1):150-172, 2005. URL: https://doi.org/10.1287/moor.1040.0112.
  11. Miroslav Chlebík and Janka Chlebíková. Hardness of approximation for orthogonal rectangle packing and covering problems. Journal of Discrete Algorithms, 7(3):291-305, 2009. URL: https://doi.org/10.1016/j.jda.2009.02.002.
  12. 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.
  13. Fan RK Chung, Michael R Garey, and David S Johnson. On packing two-dimensional bins. SIAM Journal on Algebraic Discrete Methods, 3(1):66-76, 1982. URL: https://doi.org/10.1137/0603007.
  14. Edward G. Coffman, Michael R. Garey, David S. Johnson, and Robert E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9:808-826, 1980. URL: https://doi.org/10.1137/0209062.
  15. W Fernandez De La Vega and George S. Lueker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1(4):349-355, 1981. URL: https://doi.org/10.1007/BF02579456.
  16. Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak demand minimization via sliced strip packing, 2021. URL: http://arxiv.org/abs/2105.07219.
  17. Aleksei V Fishkin, Olga Gerber, and Klaus Jansen. On efficient weighted rectangle packing with large resources. In International Symposium on Algorithms and Computation (ISAAC), pages 1039-1050. Springer, 2005. URL: https://doi.org/10.1007/11602613_103.
  18. 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 International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.44.
  19. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi. Approximation algorithms for demand strip packing, 2021. URL: http://arxiv.org/abs/2105.08577.
  20. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. In Symposium on Foundations of Computer Science (FOCS), pages 260-271. IEEE, 2017. URL: https://doi.org/10.1109/FOCS.2017.32.
  21. Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramirez-Romero, and Andreas Wiese. Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple L-shapes, spirals and more. In International Symposium on Computational Geometry (SoCG), volume 189, pages 39:1-39:17, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.39.
  22. Paul C Gilmore and Ralph E Gomory. Multistage cutting stock problems of two and more dimensions. Operations Research, 13(1):94-120, 1965. URL: https://doi.org/10.1287/opre.13.1.94.
  23. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob Van Stee. A (5/3 + ε)-approximation for strip packing. In Workshop on Algorithms and Data Structures (WADS), pages 475-487. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22300-6_40.
  24. Rebecca Hoberg and Thomas Rothvoss. A logarithmic additive integrality gap for bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2616-2625, 2017. URL: https://doi.org/10.1137/1.9781611974782.172.
  25. Klaus Jansen and Lars Prädel. New approximability results for two-dimensional bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 919-936, 2013. URL: https://doi.org/10.1007/s00453-014-9943-z.
  26. Klaus Jansen and Rob van Stee. On strip packing with rotations. In ACM Symposium on Theory of Computing (STOC), pages 755-761, 2005. URL: https://doi.org/10.1145/1060590.1060702.
  27. Klaus Jansen and Guochuan Zhang. On rectangle packing: maximizing benefits. In ACM-SIAM Symposium on Discrete Algorithms (SODA), volume 4, pages 204-213, 2004. Google Scholar
  28. Claire Kenyon and Eric Rémila. Approximate strip packing. In Symposium on Foundations of Computer Science (FOCS), pages 31-36, 1996. URL: https://doi.org/10.1109/SFCS.1996.548461.
  29. Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On guillotine separable packings for the two-dimensional geometric knapsack problem. In International Symposium on Computational Geometry (SoCG), volume 189, pages 48:1-48:17, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.48.
  30. Arindam Khan and Madhusudhan Reddy Pittu. On guillotine separability of squares and rectangles. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.47.
  31. Arindam Khan and Eklavya Sharma. Tight approximation algorithms for geometric bin packing with skewed items. ArXiv, 2105.02827, 2021. URL: http://arxiv.org/abs/2105.02827.
  32. Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas. Approximation algorithms for generalized multidimensional knapsack. ArXiv, 2102.05854, 2021. URL: http://arxiv.org/abs/2102.05854.
  33. Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas. Geometry meets vectors: Approximation algorithms for multidimensional packing. ArXiv, 2106.13951, 2021. URL: http://arxiv.org/abs/2106.13951.
  34. Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative Methods in Combinatorial Optimization, volume 46. Cambridge University Press, 2011. Google Scholar
  35. János Pach and Gábor Tardos. Cutting glass. In International Symposium on Computational Geometry (SoCG), pages 360-369, 2000. URL: https://doi.org/10.1145/336154.336223.
  36. Lars Dennis Prädel. Approximation Algorithms for Geometric Packing Problems. PhD thesis, Kiel University, 2012. URL: https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/dissertation_derivate_00004634/dissertation-praedel.pdf?AC=N.
  37. Sai Sandeep. Almost optimal inapproximability of multidimensional packing problems. ArXiv, 2101.02854, 2021. URL: http://arxiv.org/abs/2101.02854.
  38. Steven S. Seiden and Gerhard J. Woeginger. The two-dimensional cutting stock problem revisited. Mathematical Programming, 102(3):519-530, 2005. URL: https://doi.org/10.1007/s10107-004-0548-1.
  39. Eklavya Sharma. Harmonic algorithms for packing d-dimensional cuboids into bins. ArXiv, 2011.10963, 2020. URL: http://arxiv.org/abs/2011.10963.
  40. 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.
  41. Paul E. Sweeney and Elizabeth Ridenour Paternoster. Cutting and packing problems: A categorized, application-orientated research bibliography. Journal of the Operational Research Society, 43(7):691-706, 1992. URL: https://doi.org/10.1057/jors.1992.101.
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