# Partitioning a matrix into equal-sized regions: finding the maximum

I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:

• each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given,
• the sum of all elements in the matrix is 1.

The matrix is partitioned into $j$ axis-parallel non-overlapping rectangles. Each matrix cell with positive value is covered by exactly one rectangle. Whereas, each matrix cell with value 0 is covered by at most one rectangle. For each region, we sum the values inside it and obtain $region\_sum_i$, $i = 1..j$. We are given an optimal partitioning algorithm whose objective is to minimize the maximum $region\_sum_i$. The algorithm is Recursive Slice-and-Dice: Binary Space Partitions from Slice and Dice : A Simple, Improved Approximate Tiling Recipe. I need this algorithm due to the support for don't care regions and a general version of tiling problem. This is a DRTILE problem, but I translate this to RTILE using binary search.

The problem is to find an upper bound on $region\_sum_i$ for the optimal solution under worst-case input with given constraints. I need this as I am doing competitive analysis.

I appreciate any help! Many thanks!

• I'm not sure I understand the problem. Do you mean that the partition into rectangles is given? (If so, why do we need an upper bound -- we can just compute subset_sum directly, right?) Or do you mean that the partition is not given and the goal is to find a partition with the specified constraints and minimizing the maximum subset_sum? Is $j$ given? What does it mean to say you already have an algorithm for partitioning? If your algorithm computes the optimal partition, doesn't that immediately give you a tight upper bound? – D.W. Dec 6 '13 at 1:17
• I think he meant the upper bound for the optimal solution. – Chao Xu Dec 6 '13 at 1:58
• I think it be nicer if you replace $m$ with $1$, as scaling doesn't matter. Do you want an upper bound in case of the $OPT$ or in case of $j$? – Chao Xu Dec 6 '13 at 8:11
• @Chao Xu Thank you very much for your comments. I clarified the problem definition. I am not sure I understand your last question. I want an upper bound in case of OPT with given $j$. – Long Vehicle Dec 6 '13 at 8:18

In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element.
This implies a upper bound of $\frac{11}{5j}$ for your problem.
• Every solution in this partition problem(P) is a solution to your partition(YP) problem. A solution of P is an upper bound for the optimal solution of YP. Note both P and YP have a lower bound of 1/j, and the proof of the theorem shows there exist a solution where each rectangle has weight at most $\frac{11}{5j}$ for P. Thus there exist a optimal solution where all rectangles have weight at most $\frac{11}{5j}$ for YP. – Chao Xu Dec 6 '13 at 12:43
• I think I got it. The thing is that YP will not choose a worse solution than P, so $\frac{11}{5*j}$ is the upper bound. – Long Vehicle Dec 16 '13 at 15:59