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 the sum of the s_i is equal to 1), so as to minimize (i) either the sum of the p perimeters of the rectangles (ii) or the largest perimeter of the p rectangles. For both problems, we prove NP-completeness and we introduce approximation algorithms.Dans ce rapport, nous nous intéressons à deux problèmes géométriques issus de calculs parallèles hétérogèns : comment découper le carré unité en p rectangles d'aires donnés s_1, s_2,...,s_p (tel que la somme des s_i soit égale à 1), de manière à minimiser (i) soit la somme des périmètres des p rectangles (ii) soit le plus grand périmètre de ces p rectangles. Pour les deux problèmes, nous établissons leur NP-complétude et nous introduisons des algorithmes d'approximation