An approximation algorithm for dissecting a rectangle into rectangles with specified areas
From MaRDI portal
Publication:869574
DOI10.1016/j.dam.2006.08.005zbMath1107.68122MaRDI QIDQ869574
Yuusuke Abe, Hiroshi Nagamochi
Publication date: 8 March 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.005
approximation algorithm; NP-hard; aspect ratio; rectangle; facility layout; divide-and-conquer; dissection; floor plan
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
\(\gamma\)-soft packings of rectangles, An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules, On three soft rectangle packing problems with guillotine constraints, Exact and approximation algorithms for a soft rectangle packing problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The decomposition of a square into rectangles of minimal perimeter
- Improved bounds for rectangular and guillotine partitions
- On optimal guillotine partitions approximating optimal \(d\)-box partitions
- Partitioning a square into rectangles: NP-Completeness and approximation algorithms
- Tiling a rectangle with the fewest squares
- A New Mathematical-Programming Framework for Facility-Layout Design
- Optimal orientations of cells in slicing floorplan designs
- The Decomposition of a Rectangle into Rectangles of Minimal Perimeter