Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms
Olivier D.E. Beaumont, Vincent Boudet, Fabrice Rastello, Yves Robert, 69 - Lyon (France). Lab. de l'Informatique du Parallelisme Centre National de la Recherche Scientifique (CNRS), 69 (France). Lab. de l'Informatique du Parallelisme Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme Lyon-1 Univ. · 2000
In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s1, s2,...,sp (such that ∑p i=1si = 1), so as to minimize either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7 4-approximation algorithm for (i) and a (2 / √ 3)-approximation algorithm for (ii).