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
Type de document :
Communication dans un congrès
EuroMicro Workshop on Parallel and Distributed Computing (EuroMicro\'2001), 2001, Unknown, IEEE Computer Society Press, pp.298―305, 2001, 〈10.1109/EMPDP.2001.905056〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00789461
Contributeur : Arnaud Legrand <>
Soumis le : lundi 18 février 2013 - 11:51:52
Dernière modification le : mardi 16 janvier 2018 - 15:50:48

Identifiants

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, IEEE Computer Society Press, pp.298―305, 2001, 〈10.1109/EMPDP.2001.905056〉. 〈hal-00789461〉

Partager

Métriques

Consultations de la notice

138