Approximate rectangular tiling of multi-dimensional arrays
Jonathan Sharp, University of Warwick, UK

Abstract: Given a multi-dimensional array it is often desirable to
partition the array into subarrays satisfying a given property.  We focus
on the following partitioning problem: 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.  This problem is
NP-hard.  We discuss existing approximation algorithms for this and
related problems before presenting original, improved approximations
algorithms for the problems.