A tight (3/2+)-approximation for skewed strip packing

DOI10.1007/S00453-023-01130-2OpenAlexW4376139533MaRDI QIDQ6046946FDOQ6046946

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

Publication date 6 October 2023

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-023-01130-2

zbMATH Keywords

approximation algorithmsstrip packingrectangle packing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• A \((5/3 + \varepsilon )\)-approximation for strip packing
• A \((5/3+\varepsilon)\)-approximation for strip packing
• On approximating strip packing with a better ratio than 3/2
• Approximate strip packing: revisited
• A new asymptotic approximation algorithm for 3-dimensional strip packing
• An approximation scheme for strip packing of rectangles with bounded dimensions
• The problem of strip packing: An asymptotically exact approach
• Improved pseudo-polynomial-time approximation for strip packing
• An exact approach to the strip-packing problem

Cites work

• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• A 2.5 times optimal algorithm for packing in two dimensions
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A \((5/3+\varepsilon)\)-approximation for strip packing
• A near-optimal solution to a two-dimensional cutting stock problem
• A new asymptotic approximation algorithm for 3-dimensional strip packing
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• A structural lemma in 2-dimensional packing, and its implications on approximability
• Approximating Geometric Knapsack via L-packings
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation and online algorithms for multidimensional bin packing: a survey
• Asymptotically optimal scheduling of random malleable demands in smart grid
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Closing the Gap for Pseudo-Polynomial Strip Packing
• Hardness of approximation for strip packing
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Improved approximation algorithm for two-dimensional bin packing
• Improved pseudo-polynomial-time approximation for strip packing
• LATIN 2004: Theoretical Informatics
• Maximizing the total profit of rectangles packed into a rectangle
• Maximum independent set of rectangles
• New Approximability Results for 2-Dimensional Packing Problems
• On Guillotine Separability of Squares and Rectangles.
• On approximating strip packing with a better ratio than 3/2
• On strip packing with rotations
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• This side up!
• `` Strong NP-Completeness Results

Cited in

(1)

• On approximating strip packing with a better ratio than 3/2

This page was built for publication: A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing

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