3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Presumably $J$ is small? Otherwise the solution would be to enclose each cell in its own square... $\endgroup$ – Joseph O'Rourke Sep 10 '13 at 15:27
  • $\begingroup$ And presumably $a > 0$, otherwise all covers have equal weight. $\endgroup$ – Joseph O'Rourke Sep 10 '13 at 23:45
  • $\begingroup$ 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 $\endgroup$ – SaSa Sep 11 '13 at 13:47
  • 1
    $\begingroup$ @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? $\endgroup$ – domotorp Sep 13 '13 at 15:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Long Vehicle Sep 17 '13 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.