# Tiling a rectangle with weighted cells (min-max problem)

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

Presumably $J$ is small? Otherwise the solution would be to enclose each cell in its own square... – Joseph O'Rourke Sep 10 '13 at 15:27
And presumably $a > 0$, otherwise all covers have equal weight. – Joseph O'Rourke Sep 10 '13 at 23:45