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

Olivier Beaumont 1 Vincent Boudet 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 s₁, s₂,..., sₚ (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.
Complete list of metadatas

https://hal.inria.fr/hal-00856643
Contributor : Equipe Roma <>
Submitted on : Monday, September 2, 2013 - 10:21:57 AM
Last modification on : Friday, November 23, 2018 - 1:40:03 PM

Identifiers

  • HAL Id : hal-00856643, version 1

Collections

Citation

Olivier Beaumont, Vincent Boudet, Fabrice Rastello, Yves Robert. Heterogeneous Matrix-Matrix Multiplication or Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms. [Research Report] 2000-10, 2000. ⟨hal-00856643⟩

Share

Metrics

Record views

228