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

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_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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101984
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:22 AM
Last modification on : Wednesday, May 8, 2019 - 1:34:28 AM

File

RR2000-10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101984, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

12

Files downloads

61