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.
Type de document :
Rapport
[Research Report] 2000-10, 2000
Liste complète des métadonnées

https://hal.inria.fr/hal-00856643
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 10:21:57
Dernière modification le : mardi 16 janvier 2018 - 15:50:56

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

178