论文标题
矩形瓷砖二进制阵列
Rectangle Tiling Binary Arrays
论文作者
论文摘要
矩形瓷砖二进制阵列的问题定义如下。鉴于$ n \ times n $ array $ a $ a $零和一个自然数量$ p $，我们的任务是将$ a $划分为最多$ p $矩形瓷砖，以使瓷砖的最大重量最小化。瓷砖是$ a $的任何矩形子阵列。瓷砖的重量是其中的元素之和。我们提出一个线性$（o（n^2））$ time $（\ frac {3} {2}+\ frac {p^2} {w（a）}）$ - 近似值算法（$ \ frac {p^2}}整个阵列$ a $。这改善了先前已知的近似值，比率$ 2 $。 从以下意义上讲，结果是最好的。该算法采用$ l = \ lceil \ frac {w（a）} {p} \ rceil $的下限，这是矩形瓷砖的所有算法中唯一已知和使用的最佳限制。我们证明，无法使用$ l $来实现二进制\ rtile的更好近似因素，因为存在数组，每个分区都包含一个重量的瓷砖，至少$（\ frac {3} {2} {2} {2}+\ frac {p^2} {w（a）} {w（a）} {w（a）}）l $。我们还考虑了二进制阵列的矩形瓷砖的双重问题，在那里我们将在瓷砖的重量上给出上限，并且我们必须覆盖数组$ a $，并使用最少的非重叠瓷砖数量。这两个问题都具有自然扩展到$ d $维的版本，我们为此提供了类似的结果。
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.
