A \((5/3+\varepsilon)\)-approximation for strip packing
From MaRDI portal
Publication:390133
DOI10.1016/j.comgeo.2013.08.008zbMath1283.52024OpenAlexW2098666887MaRDI QIDQ390133
Rob van Stee, Rolf Harren, Klaus Jansen, Lars Prädel
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
Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25)
Related Items (21)
Packing anchored rectangles ⋮ On the Approximability of Orthogonal Order Preserving Layout Adjustment ⋮ A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons ⋮ A new lower bound for online strip packing ⋮ On the number of anchored rectangle packings for a planar point set ⋮ On the Number of Anchored Rectangle Packings for a Planar Point Set ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ iGreen: green scheduling for peak demand minimization ⋮ A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing ⋮ On contiguous and non-contiguous parallel task scheduling ⋮ High multiplicity strip packing with three rectangle types ⋮ Unnamed Item ⋮ An improved approximation for packing big two-bar charts ⋮ A Tight (3/2+ε) Approximation for Skewed Strip Packing. ⋮ New upper bounds for online strip packing ⋮ Online square-into-square packing ⋮ Improved approximation for two dimensional strip packing with polynomial bounded width ⋮ Complexity and inapproximability results for parallel task scheduling and strip packing ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ Two-bar charts packing problem
Cites Work
- Rectangle packing with one-dimensional resource augmentation
- Maximizing the total profit of rectangles packed into a rectangle
- A 2.5 times optimal algorithm for packing in two dimensions
- 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
- A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
- Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
- Orthogonal Packings in Two Dimensions
- Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
- A algorithm for two-dimensional packing
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Approximation Algorithms for Scheduling Parallel Jobs
This page was built for publication: A \((5/3+\varepsilon)\)-approximation for strip packing
