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

被引:0
作者
机构
[1] LIP,
[2] UMR CNRS-ENS Lyon-INRIA 5668,undefined
[3] Ecole Normale Supérieure de Lyon,undefined
[4] F-69364 Lyon Cedex 07,undefined
[5] France. Contact: Yves.Robert@ens-lyon.fr.,undefined
来源
Algorithmica | 2002年 / 34卷
关键词
Key words. NP-completeness, Approximation algorithms, Geometric problems, Heterogeneous resources, Parallel computing.;
D O I
暂无
中图分类号
学科分类号
摘要
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 either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7/4 -approximation algorithm for (i) and a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $(2/\sqrt{3})$ \end{document} -approximation algorithm for (ii).
引用
收藏
页码:217 / 239
页数:22
相关论文
empty
未找到相关数据