The Library
Tiling multi-dimensional arrays
Tools
UNSPECIFIED (1999) Tiling multi-dimensional arrays. In: 12th International Symposium on Fundamental of Computation Theory, IASI, ROMANIA, AUG 30-SEP 03, 1999. Published in: FUNDAMENTALS OF COMPUTATION THEORY, 1684 pp. 500-511. ISBN 3-540-66412-2. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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 | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-66412-2 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Ciobanu, G and Paun, G | ||||
Official Date: | 1999 | ||||
Dates: |
|
||||
Volume: | 1684 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 500-511 | ||||
Publication Status: | Published | ||||
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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |