The Library
Tiling multidimensional arrays
Tools
UNSPECIFIED (1999) Tiling multidimensional arrays. In: 12th International Symposium on Fundamental of Computation Theory, IASI, ROMANIA, AUG 30SEP 03, 1999. Published in: FUNDAMENTALS OF COMPUTATION THEORY, 1684 pp. 500511.
Full text not available from this repository.Abstract
We continue the study of the tiling problems introduced in [KMP98]. The first problem we consider is: given a ddimensional array of nonnegative numbers and a tile limit p, partition the array into at most p rectangular, nonoverlapping 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 onedimensional arrays the problem can be solved optimally in polynomial time, whereas for twodimensional arrays it is shown in [KMP98] that the problem is NPhard and an approximation algorithm is given. This paper offers a new (d(2) + 2d1)/(2d  1) approximation algorithm for the ddimensional problem (d greater than or equal to 2), which improves the (d + 3)/2 approximation algorithm given in [SS99]. In particular, for twodimensional 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:  SPRINGERVERLAG BERLIN  
ISBN:  3540664122  
ISSN:  03029743  
Editor:  Ciobanu, G and Paun, G  
Official Date:  1999  
Dates: 


Volume:  1684  
Number of Pages:  12  
Page Range:  pp. 500511  
Publication Status:  Published  
Title of Event:  12th International Symposium on Fundamental of Computation Theory  
Location of Event:  IASI, ROMANIA  
Date(s) of Event:  AUG 30SEP 03, 1999  
URI:  http://wrap.warwick.ac.uk/id/eprint/12814 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 