Rectangular Tiling in Multidimensional Arrays

✍ Scribed by Adam Smith; Subhash Suri

• Book ID: 102573651
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 168 KB
• Volume: 37
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1109

✦ Synopsis

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of nonnegative numbers and an integer p, partition the array into at most p rectangular subarrays so that the maximum weight of any subarray is minimized; the weight of a subarray is the sum of its elements. The rectangular tiling problem is motivated by applications in data mining, data partitioning, and w x video compression. Recently, Khanna, Muthukrishnan, and Paterson SODA '98 , showed that the tiling problem is NP-complete and gave a 2.5-approximation algorithm for d s 2.

In this paper, we extend their result to multidimensional arrays and give an d q 3 Ž . algorithm with approximation ratio , for d G 2. The algorithm can be 2 Ž . implemented to run in worst-case time O N q p log N time, where N is the size of the array, and the constant is of the order d!. We also obtain a similar algorithm for the dual tiling problem, where the goal is to compute a tiling of weight at most W using as few tiles as possible. Our algorithm yields an approximation factor Ž . 2 d q 1 . We implemented our algorithm and ran simulation tests on multidimensional arrays with random data. In our limited experiments, the algorithm always produced approximations that were no worse than factor two from the optimal.