Tight approximation algorithms for 2D guillotine strip packing

DOI10.1145/3736723MaRDI QIDQ6922354zbMATH OpenFDO

Authors Arindam Khan, Arnab Maiti, Amatya Sharma, Andreas Wiese

Publication date 1 October 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3736723

zbMATH Keywords

approximation algorithmscomputational geometryguillotine cutsrectangle packingtwo-dimensional packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• OPTVersusLOADin Dynamic Storage Allocation
• `` Strong NP-Completeness Results
• A 2.5 times optimal algorithm for packing in two dimensions
• A 3-approximation algorithm for maximum independent set of rectangles
• A (5/3+)-approximation for strip packing
• A bidirectional building approach for the 2D constrained guillotine knapsack packing problem
• A near-optimal solution to a two-dimensional cutting stock problem
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• An Algorithm for Two-Dimensional Cutting Problems
• An EDA for the 2D knapsack problem with guillotine constraint
• Approximating Geometric Knapsack via L-packings
• Approximating maximum independent set for rectangles in the plane
• Approximation Algorithms for Demand Strip Packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation schemes for independent set and sparse subsets of polygons
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Closing the Gap for Pseudo-Polynomial Strip Packing
• Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem
• Complexity and inapproximability results for parallel task scheduling and strip packing
• Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
• Cutting glass
• Exact algorithms for the two-dimensional guillotine knapsack
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• Improved approximation algorithm for two-dimensional bin packing
• Improved pseudo-polynomial-time approximation for strip packing
• Modeling two-dimensional guillotine cutting problems via integer programming
• Multistage Cutting Stock Problems of Two and More Dimensions
• On approximating strip packing with a better ratio than 3/2
• On guillotine cutting sequences
• On Guillotine Separability of Squares and Rectangles.
• On rectangle packing, maximizing benefits
• Orthogonal Packings in Two Dimensions
• Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints
• Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
• Peak demand minimization via sliced strip packing
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• The two-dimensional cutting stock problem revisited
• Tight approximation algorithms for geometric bin packing with skewed items

This page was built for publication: Tight approximation algorithms for 2D guillotine strip packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6922354)