Tiling multi-dimensional arrays
UNSPECIFIED (1999) Tiling multi-dimensional arrays. In: 12th International Symposium on Fundamental of Computation Theory, AUG 30-SEP 03, 1999, IASI, ROMANIA.Full text not available from this repository.
We continue the study of the tiling problems introduced in [KMP98]. The first problem we consider is: given a d-dimensional array of non-negative numbers and a tile limit p, partition the array into at most p rectangular, non-overlapping subarrays, referred to as tiles, in such a way as to minimise the weight of the heaviest tile, where the weight of a tile is the sum of the elements that fall within it. For one-dimensional arrays the problem can be solved optimally in polynomial time, whereas for two-dimensional arrays it is shown in [KMP98] that the problem is NP-hard and an approximation algorithm is given. This paper offers a new (d(2) + 2d-1)/(2d - 1) approximation algorithm for the d-dimensional problem (d greater than or equal to 2), which improves the (d + 3)/2 approximation algorithm given in [SS99]. In particular, for two-dimensional arrays, our approximation ratio is 7/3 improving on the ratio of 5/2 in [KMP98] and [SS99]. We briefly consider the dual tiling problem where, rather than having a limit on the number of tiles allowed, we must ensure that all tiles produced have weight at most W and do so with a minimal number of tiles. The algorithm for the first problem can be modified to give a 2d approximation for this problem improving upon the 2d + 1 approximation given in [SS99]. These problems arise naturally in many applications including databases and load balancing.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||FUNDAMENTALS OF COMPUTATION THEORY|
|Editor:||Ciobanu, G and Paun, G|
|Number of Pages:||12|
|Page Range:||pp. 500-511|
|Title of Event:||12th International Symposium on Fundamental of Computation Theory|
|Location of Event:||IASI, ROMANIA|
|Date(s) of Event:||AUG 30-SEP 03, 1999|
Actions (login required)