Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by exactly one rectangle, and a $0$-cell is covered by at most one rectangle. Given that weight of a rectangle is $a * \mbox{perimeter} + b* \mbox{sum_of_cell_values_inside}$, design an algorithm which minimizes the maximum weight of a rectangle.

Ideally, we would like an approximation algorithm with competitive ratio=2 and $O(n \log n)$ time complexity. We would be fine with probabilistic guarantees.

The matrix is sparse, that is the number of non-zero elements in the matrix is $O(n \log n)$. In addition, $a, b > 0$, $J \ll n$.

We posed the same question on MathOverflow.

We hope anyone can give us any leads on this problem. Thanks a lot :)

  • 1
    $\begingroup$ First this problem should be solved for a=0 and for b=0, until then there is no point in attacking the general problem. $\endgroup$ – domotorp Nov 9 '13 at 10:05
  • $\begingroup$ Ok, a=0 is pretty easy to 2-approximate, but I don't know about b=0. $\endgroup$ – domotorp Nov 9 '13 at 10:19

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.