A Strip-Packing Algorithm with Absolute Performance Bound 2
From MaRDI portal
Publication:4337640
DOI10.1137/S0097539793255801zbMath0874.68140OpenAlexW2059422698MaRDI QIDQ4337640
No author found.
Publication date: 26 May 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793255801
Related Items (63)
Packing anchored rectangles ⋮ Rectangle packing with one-dimensional resource augmentation ⋮ UPS-\(k\): a set partitioning problem with applications in UPS pickup-delivery system ⋮ Coordination Mechanisms for Selfish Parallel Jobs Scheduling ⋮ Strip packing with precedence constraints and strip packing with release times ⋮ 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 ⋮ APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS ⋮ A new lower bound for online strip packing ⋮ Two for One: Tight Approximation of 2D Bin Packing ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ Approximate composable truthful mechanism design ⋮ Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem ⋮ Packing into the smallest square: worst-case analysis of lower bounds ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On-line scheduling mesh jobs with dependencies ⋮ Scheduling parallel jobs to minimize the makespan ⋮ The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview ⋮ A \((5/3+\varepsilon)\)-approximation for strip packing ⋮ On-line scheduling of parallel jobs ⋮ A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ Peak demand minimization via sliced strip packing ⋮ On contiguous and non-contiguous parallel task scheduling ⋮ Online multiple-strip packing ⋮ An improved approximation algorithm for scheduling monotonic moldable tasks ⋮ High multiplicity strip packing with three rectangle types ⋮ Efficient approximation algorithms for scheduling moldable tasks ⋮ Packing Rectangles into 2OPT Bins Using Rotations ⋮ An improved approximation for packing big two-bar charts ⋮ An approximation scheme for the two-stage, two-dimensional knapsack problem ⋮ An effective approximation algorithm for the malleable parallel task scheduling problem ⋮ Absolute approximation ratios for packing rectangles into bins ⋮ Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width ⋮ Online square packing with gravity ⋮ On the two-dimensional knapsack problem ⋮ Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing ⋮ Relations between capacity utilization, minimal bin size and bin number ⋮ Improved approximation algorithms for scheduling parallel jobs on identical clusters ⋮ On-line scheduling of parallel jobs in a list ⋮ A Tight (3/2+ε) Approximation for Skewed Strip Packing. ⋮ New upper bounds for online strip packing ⋮ TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING ⋮ Recent advances on two-dimensional bin packing problems ⋮ A 3-approximation algorithm for two-dimensional bin packing ⋮ An approximation algorithm for square packing. ⋮ Average-case performance analysis of a 2D strip packing algorithm -- NFDH ⋮ Improved approximation for two dimensional strip packing with polynomial bounded width ⋮ Complexity and inapproximability results for parallel task scheduling and strip packing ⋮ A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks ⋮ The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio ⋮ Upper bounds for heuristic approaches to the strip packing problem ⋮ Approximation algorithms for two-stage flexible flow shop scheduling ⋮ Upper Bounds for Heuristic Approaches to the Strip Packing Problem ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ Two-bar charts packing problem ⋮ Approximability results for the resource-constrained project scheduling problem with a single type of resources ⋮ A note on online strip packing ⋮ Two-dimensional packing problems: a survey ⋮ An approximation algorithm for scheduling trees of malleable tasks ⋮ Global optimization approach to unequal global optimization approach to unequal sphere packing problems in 3D ⋮ New approximability results for two-dimensional bin packing
This page was built for publication: A Strip-Packing Algorithm with Absolute Performance Bound 2
