zbMATH — the first resource for mathematics

Rectangle tiling. (English) Zbl 0976.90084
Jansen, Klaus (ed.) et al., Approximation algorithms for combinatorial optimization. 3rd international workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1913, 206-213 (2000).
Summary: We consider two tiling problems for two-dimensional arrays: given an \(n\times n\) array \(A\) of nonnegative numbers we are to construct an optimal partition of it into rectangular subarrays. The subarrays cannot overlap and they have to cover all array elements. The first problem (RTILE) consists in finding a partition using \(p\) subarrays that minimizes the maximum weight of subarrays (by weight we mean the sum of all elements covered by the subarray). The second, dual problem (DRTILE), is to construct a partition into minimal number of subarrays such that the weight of each subarray is bounded by a given value \(W\).
We show a linear-time \(7/3\)-approximation algorithm for the RTILE problem. This improves the best previous result both in time and in approximation ratio. If the array \(A\) is binary (i.e. contains only zeroes and ones) we can reduce the approximation ratio up to 2. For the DRTILE problem we get an algorithm which achieves a ratio 4 and works in linear-time. The previously known algorithm with the same ratio worked in time \(O(n^5)\). For binary arrays we present a linear-time 2-approximation algorithm.
For the entire collection see [Zbl 0947.00047].
90C27 Combinatorial optimization
05B45 Combinatorial aspects of tessellation and tiling problems
68W25 Approximation algorithms