Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

DOI10.1007/978-3-642-03685-9_14MaRDI QIDQ3638877zbMATH OpenOpenAlexFDO

Authors Rolf Harren, Rob van Stee

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

zbMATH Keywords

approximation algorithmstrip packingrectangle packingtwo-dimensional bin packingabsolute worst-case ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• New Approximability Results for 2-Dimensional Packing Problems
• Improved approximation algorithm for two-dimensional bin packing
• scientific article; zbMATH DE number 1263202
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• New approximability results for two-dimensional bin packing
• New approximability results for two-dimensional bin packing
• Absolute approximation ratios for packing rectangles into bins
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Approximation schemes for multidimensional packing
• scientific article; zbMATH DE number 2086931

Cited in

(20)

• Closing the Gap for Pseudo-Polynomial Strip Packing
• New upper bounds for online strip packing
• New approximability results for two-dimensional bin packing
• On the approximability of orthogonal order preserving layout adjustment
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• A \((5/3+\varepsilon)\)-approximation for strip packing
• An improved approximation for packing big two-bar charts
• On strip packing with rotations
• Approximation and online algorithms for multidimensional bin packing: a survey
• Peak demand minimization via sliced strip packing
• An improved approximation algorithm for scheduling monotonic moldable tasks
• A new lower bound for online strip packing
• Polynomial-time approximation schemes for circle and other packing problems
• Two-bar charts packing problem
• Absolute approximation ratios for packing rectangles into bins
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• New Approximability Results for 2-Dimensional Packing Problems
• High multiplicity strip packing with three rectangle types
• Offline first-fit decreasing height scheduling of power loads

This page was built for publication: Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

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