# 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.

**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 |

Official 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 or add full text files to a record

### Actions (login required)

View Item |