Hardness of approximation for orthogonal rectangle packing and covering problems
From MaRDI portal
Publication:1026242
DOI10.1016/j.jda.2009.02.002zbMath1178.68282MaRDI QIDQ1026242
Miroslav Chlebík, Janka Chlebíková
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
inapproximability results; rectangle covering; orthogonal rectangle packing; packing and covering with rotations
52C15: Packing and covering in (2) dimensions (aspects of discrete geometry)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
52C17: Packing and covering in (n) dimensions (aspects of discrete geometry)
68W25: Approximation algorithms
Related Items
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
