A (5/3+)-approximation for strip packing
From MaRDI portal
Publication:390133
DOI10.1016/J.COMGEO.2013.08.008zbMATH Open1283.52024OpenAlexW2098666887MaRDI QIDQ390133FDOQ390133
Authors: Rolf Harren, Klaus Jansen, Lars Prädel, Rob van Stee 
Publication date: 22 January 2014
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2013.08.008
Recommendations
- A \((5/3 + \varepsilon )\)-approximation for strip packing
- On approximating strip packing with a better ratio than 3/2
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- An approximation scheme for strip packing of rectangles with bounded dimensions
- New Approximability Results for 2-Dimensional Packing Problems
Approximation algorithms (68W25) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)
Cites Work
- A near-optimal solution to a two-dimensional cutting stock problem
- Two for One: Tight Approximation of 2D Bin Packing
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
- Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Rectangle packing with one-dimensional resource augmentation
- Maximizing the total profit of rectangles packed into a rectangle
- A structural lemma in 2-dimensional packing, and its implications on approximability
- Orthogonal Packings in Two Dimensions
- A algorithm for two-dimensional packing
- A 2.5 times optimal algorithm for packing in two dimensions
- Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
- Approximation algorithms for scheduling parallel jobs
Cited In (32)
- New upper bounds for online strip packing
- On the approximability of orthogonal order preserving layout adjustment
- Approximating minimum-area rectangular and convex containers for packing convex polygons
- A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
- Complexity and inapproximability results for parallel task scheduling and strip packing
- A Tight (3/2+ε) Approximation for Skewed Strip Packing.
- Packing anchored rectangles
- An improved approximation for packing big two-bar charts
- A posteriori analysis of the algorithms for two-bar charts packing problem
- On the number of anchored rectangle packings for a planar point set
- Hardness of approximation for strip packing
- A new asymptotic approximation algorithm for 3-dimensional strip packing
- Approximation and online algorithms for multidimensional bin packing: a survey
- A PTAS for the horizontal rectangle stabbing problem
- Improved pseudo-polynomial-time approximation for strip packing
- A \((5/3 + \varepsilon )\)-approximation for strip packing
- A new lower bound for online strip packing
- Two-bar charts packing problem
- On contiguous and non-contiguous parallel task scheduling
- Improved approximation for two dimensional strip packing with polynomial bounded width
- (Re)packing equal disks into rectangle
- A note on the Kenyon-Remila strip-packing algorithm
- A near-optimal solution to a two-dimensional cutting stock problem
- iGreen: green scheduling for peak demand minimization
- On the number of anchored rectangle packings for a planar point set
- A harmonic algorithm for the 3D strip packing problem
- Online strip packing with polynomial migration
- Approximation algorithms for multiple strip packing
- High multiplicity strip packing with three rectangle types
- Online square-into-square packing
- Closing the Gap for Pseudo-Polynomial Strip Packing
- On approximating strip packing with a better ratio than 3/2
This page was built for publication: A \((5/3+\varepsilon)\)-approximation for strip packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390133)
