# 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

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)

-
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
yes J is small. That is J<< n and a and b are just weights whose values range between 0 and 1. That is 0<= a,b <=1 – SaSa Sep 11 '13 at 13:47
@SaSa: what do you mean by partition? imo in a partition every cell is covered exactly once. do you want every cell covered at most once (and at least once if it's positive)? also, do you know the answer for a=0 or b=0? – domotorp Sep 13 '13 at 15:25
I am Sasa's collaborator, and I'll try to clarify the problem statement. @domotorp: 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. – Long Vehicle Sep 17 '13 at 7:47