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.

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
Date:	1999
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
URI:	http://wrap.warwick.ac.uk/id/eprint/12814

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item