Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms

Résumé

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_1, s_2,..., s_p (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.
Dans ce rapport, nous nous intéressons à deux problèmes géométriques issus de calculs parallèles hétérogèns : comment découper le carré unité en p rectangles d'aires donnés s_1, s_2,...,s_p (tel que la somme des s_i soit égale à 1), de manière à minimiser (i) soit la somme des périmètres des p rectangles (ii) soit le plus grand périmètre de ces p rectangles. Pour les deux problèmes, nous établissons leur NP-complétude et nous introduisons des algorithmes d'approximation.
Fichier principal
Vignette du fichier
RR2000-10.pdf (421.21 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101984 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101984 , version 1

Citer

Olivier Beaumont, Vincent Boudet, Fabrice Rastello, Yves Robert. Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms. [Research Report] LIP RR-2000-10, Laboratoire de l'informatique du parallélisme. 2000, 2+25 p. ⟨hal-02101984⟩
52 Consultations
1867 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More