New Approximability Results for 2-Dimensional Packing Problems

DOI10.1007/978-3-540-74456-6_11MaRDI QIDQ3525560zbMATH OpenOpenAlexFDO

Authors Roberto Solis-Oba, Klaus Jansen

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_11

Mathematics Subject Classification ID

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

Recommendations

• New approximability results for two-dimensional bin packing
• New approximability results for two-dimensional bin packing
• New approximability and inapproximability results for 2-dimensional bin packing
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Two-dimensional packing problems: a survey
• Recent advances on two-dimensional bin packing problems
• A structural lemma in 2-dimensional packing, and its implications on approximability
• The two-dimensional finite bin packing problem. II: New lower and upper bounds
• Improved approximation algorithm for two-dimensional bin packing
• New bounds for multidimensional packing

Cited in

(30)

• New approximability results for two-dimensional bin packing
• Approximation algorithms for orthogonal packing problems for hypercubes
• scientific article; zbMATH DE number 3942360 (Why is no real title available?)
• 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
• Approximation schemes for generalized two-dimensional vector packing with application to data placement
• Rectangle packing with one-dimensional resource augmentation
• Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
• A \((2+\varepsilon)\)-approximation algorithm for the storage allocation problem
• On strip packing with rotations
• Approximation and online algorithms for multidimensional bin packing: a survey
• A new upper bound for unconstrained two-dimensional cutting and packing
• A \((5/3 + \varepsilon )\)-approximation for strip packing
• A structural lemma in 2-dimensional packing, and its implications on approximability
• Absolute approximation ratios for packing rectangles into bins
• A new nonlinear model for the two-dimensional rectangle packing problem
• An approximation scheme for strip packing of rectangles with bounded dimensions
• A note on the Kenyon-Remila strip-packing algorithm
• Coordination mechanisms for selfish parallel jobs scheduling (extended abstract)
• A near-optimal solution to a two-dimensional cutting stock problem
• LATIN 2004: Theoretical Informatics
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• Two for One: Tight Approximation of 2D Bin Packing
• Packing Rectangles into 2OPT Bins Using Rotations
• Parameterized complexity of strip packing and minimum volume packing
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Approximation algorithms for multiple strip packing
• A Polynomial Time Approximation Scheme for the Square Packing Problem
• High multiplicity strip packing with three rectangle types

This page was built for publication: New Approximability Results for 2-Dimensional Packing Problems

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