Hardness of approximation for orthogonal rectangle packing and covering problems

DOI10.1016/j.jda.2009.02.002zbMath1178.68282OpenAlexW2045601300MaRDI QIDQ1026242

Janka Chlebíková, Miroslav Chlebík

Publication date: 24 June 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2009.02.002

zbMATH Keywords

inapproximability resultsrectangle coveringorthogonal rectangle packingpacking and covering with rotations

Mathematics Subject Classification ID

Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Approximation algorithms (68W25)

Related Items (9)

Packing anchored rectangles ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ There is no APTAS for 2-dimensional vector bin packing: revisited ⋮ A space-indexed formulation of packing boxes into a larger box ⋮ Exploiting Packing Components in General-Purpose Integer Programming Solvers ⋮ A multi-objective genetic algorithm for a special type of 2D orthogonal packing problems ⋮ TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING ⋮ Optimal clustering of a pair of irregular objects ⋮ New approximability results for two-dimensional bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• There is no asymptotic PTAS for two-dimensional vector packing
• An on-line algorithm for multidimensional bin packing
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Bin packing can be solved within 1+epsilon in linear time
• The hardness of approximation: Gap location
• An asymptotic fully polynomial time approximation scheme for bin covering.
• Complexity of approximating bounded variants of optimization problems
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
• On Three-Dimensional Packing
• On strip packing With rotations
• An asymptotic approximation algorithm for 3D-strip packing
• Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• LATIN 2004: Theoretical Informatics

This page was built for publication: Hardness of approximation for orthogonal rectangle packing and covering problems