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!