Closing the Gap for Pseudo-Polynomial Strip Packing

DOI10.4230/LIPICS.ESA.2019.62MaRDI QIDQ5075807zbMATH OpenOpenAlexFDO

Authors Malin Rau, Klaus Jansen

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1712.04922

zbMATH Keywords

90 degree rotationcontiguous moldable task schedulingpseudo-polynomialstrip packing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Improved pseudo-polynomial-time approximation for strip packing
• On approximating strip packing with a better ratio than 3/2
• A (5/3 + )-approximation for strip packing

Cites work

• A \frac32‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• A 2.5 times optimal algorithm for packing in two dimensions
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• A (5/3+)-approximation for strip packing
• A (5/3+)-approximation for unsplittable flow on a path: placing small tasks into boxes
• A algorithm for two-dimensional packing
• A near-optimal solution to a two-dimensional cutting stock problem
• A note on the Kenyon-Remila strip-packing algorithm
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms
• Approximation algorithms for scheduling parallel jobs
• Approximation and online algorithms for multidimensional bin packing: a survey
• Faster approximation schemes for the two-dimensional knapsack problem
• Hardness of approximation for strip packing
• scientific article; zbMATH DE number 1003247 (Why is no real title available?)
• scientific article; zbMATH DE number 6820261 (Why is no real title available?)
• 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
• On approximating strip packing with a better ratio than 3/2
• On the optimality of approximation schemes for the classical scheduling problem
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
• Rectangle packing with one-dimensional resource augmentation
• To augment or not to augment: solving unsplittable flow on a path by creating slack

Cited in

(14)

• Exact solution techniques for two-dimensional cutting and packing
• Approximate strip packing: revisited
• An improved algorithm for parallel machine scheduling under additional resource constraints
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• Peak demand minimization via sliced strip packing
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• An improved approximation algorithm for scheduling monotonic moldable tasks
• Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms
• Algorithms for scheduling deadline-sensitive malleable tasks
• Tight approximation algorithms for 2D guillotine strip packing
• Scheduling moldable tasks on homogeneous multi-cluster platforms with GPUs
• Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
• Improved approximation guarantees for advertisement placement
• Improved approximation algorithms for three-dimensional bin packing

This page was built for publication: Closing the Gap for Pseudo-Polynomial Strip Packing

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