I have been struggling with a research problem. The problem can be formalized as follows:

Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ rectangles, such that each non-zero cell is covered **once** (non overlapping cover), and zero cell may or may not be covered by a rectangle. Given that weight of a rectangle is $a \cdot\text{perimeter}$ + $b\cdot \text{sum_of_cell_values_inside}$, design an algorithm which minimizes the maximum weight of a rectangle.

Ideally we are seeking for an approximation algorithm with at most a poly-logarithmic cost in terms of n or m. That said, ideally, we would like an approximation algorithm with competitive ratio=$2$ and $O(n\log n+m\log m)$ time complexity.

I hope anyone can give us some leads for solving this problem

Comments:

It is allowed that either a or b is equal to 0, but not both of them. Setting one of these constants to zero simplifies the problem, so we are actually interested in the general case, 0 < a, b <= 1. Partition means that all the positive cells are covered exactly once, and zero cells are covered at most once.

J<< n and a and b are just weights whose values range between 0 and 1. That is 0<= a,b <=1

The matrix is sparse, that is the number of non-zero elements in the matrix is O(nlogn + mlogm)