A New Approximation Algorithm for Multidimensional Rectangle Tiling
A New Approximation Algorithm for Multidimensional Rectangle Tiling
复制标题
一种新的多维矩形平铺近似算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Katarzyna E. Paluch
中科院分区：
文献类型：
--
作者：
Katarzyna E. Paluch
We consider the following tiling problem: Given a d dimensional array A of size n in each dimension, containing non-negative numbers and a positive integer p, partition the array A into at most p disjoint rectangular subarrays called rectangles so as to minimise the maximum weight of any rectangle. The weight of a subarray is the sum of its elements.
In the paper we give a $frac{d+2}{2}$-approximation algorithm that is tight with regard to the only known and used lower bound so far.
