Partitioning a Square into Rectangles: NP‐Completeness and Approximation Algorithms

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 s 1 , s 2 ,…,s p (such that Σ i=1 ^p s i = 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/\sqrt{3})$ ‐approximation algorithm for (ii).