Heterogeneous Matrix-Matrix Multiplication or Partitioning a Square into Rectangles: NP- Completeness and Approximation Algorithms

In this pape6 we deal with n ~ o geometric problems arising froin heterogeneous parallel computing: how to partition the unit square irito p rectangles of given area SI, sa,... sp (such that E:='=, s = l), so as to mini-mize (i) either the sum of the p perimeters of the rect-angles (i i) or the largest perimeter of the p rectangles. For both problems, we prove NP-completeness and we introduce approximation algorithms.