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

Olivier Beaumont 1 Vincent Boudet 1 Arnaud Legrand 1 Fabrice Rastello 1 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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 Σi=1p si=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
Complete list of metadatas

https://hal.inria.fr/hal-00789461
Contributor : Arnaud Legrand <>
Submitted on : Monday, February 18, 2013 - 11:51:52 AM
Last modification on : Friday, November 23, 2018 - 1:40:03 PM

Links full text

Identifiers

Collections

Citation

Olivier Beaumont, Vincent Boudet, Arnaud Legrand, Fabrice Rastello, Yves Robert. Heterogeneous Matrix-Matrix Multiplication, or Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms. EuroMicro Workshop on Parallel and Distributed Computing (EuroMicro\'2001), 2001, Unknown, pp.298―305, ⟨10.1109/EMPDP.2001.905056⟩. ⟨hal-00789461⟩

Share

Metrics

Record views

174