  The problem of rectangle tiling binary arrays is defined as follows. Given an
$n \times n$ array $A$ of zeros and ones and a natural number $p$, our task is
to partition $A$ into at most $p$ rectangular tiles, so that the maximal weight
of a tile is minimized. A tile is any rectangular subarray of $A$. The weight
of a tile is the sum of elements that fall within it. We present a linear
$(O(n^2))$ time $(\frac{3}{2}+\frac{p^2}{w(A)})$-approximation algorithm (where
$\frac{p^2}{w(A)} < \frac{1}{2}$) for this problem, where $w(A)$ denotes the
weight of the whole array $A$. This improves on the previously known
approximation with the ratio $2$.
  The result is best possible in the following sense. The algorithm employs the
lower bound of $L=\lceil \frac{w(A)}{p} \rceil$, which is the only known and
used bound on the optimum in all algorithms for rectangle tiling. We prove that
a better approximation factor for the binary \RTILE cannot be achieved using
$L$, because there exist arrays, whose every partition contains a tile with
weight at least $(\frac{3}{2}+\frac{p^2}{w(A)})L$. We also consider the dual
problem of rectangle tiling for binary arrays, where we are given an upper
bound on the weight of the tiles, and we have to cover the array $A$ with the
minimum number of non-overlapping tiles. Both problems have natural extensions
to $d$-dimensional versions, for which we provide analogous results.
