Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
From MaRDI portal
Publication:3638877
DOI10.1007/978-3-642-03685-9_14zbMath1255.68304OpenAlexW1586863324MaRDI QIDQ3638877
Publication date: 28 October 2009
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_14
approximation algorithmstrip packingrectangle packingtwo-dimensional bin packingabsolute worst-case ratio
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (18)
On the Approximability of Orthogonal Order Preserving Layout Adjustment ⋮ A new lower bound for online strip packing ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A \((5/3+\varepsilon)\)-approximation for strip packing ⋮ A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing ⋮ Peak demand minimization via sliced strip packing ⋮ An improved approximation algorithm for scheduling monotonic moldable tasks ⋮ High multiplicity strip packing with three rectangle types ⋮ An improved approximation for packing big two-bar charts ⋮ Offline first-fit decreasing height scheduling of power loads ⋮ A Tight (3/2+ε) Approximation for Skewed Strip Packing. ⋮ New upper bounds for online strip 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 ⋮ New approximability results for two-dimensional bin packing
This page was built for publication: Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
