Heterogeneous Matrix-Matrix Multiplication or Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2000

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

(1) , (1) , (1) , (1)
1
Vincent Boudet
Fabrice Rastello
Yves Robert

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.
Not file

Dates and versions

hal-00856643 , version 1 (02-09-2013)

Identifiers

  • HAL Id : hal-00856643 , version 1

Cite

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⟩
75 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More