<p>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.</p>

<p>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.</p>

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

<p>We posed the same question on <a href="https://mathoverflow.net/questions/141797/tiling-a-rectangle-with-weighted-cells-min-max-problem?noredirect=1#comment375379_141797">MathOverflow</a>.</p>

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

CC BY-SA 3.0
2013-11-09T10:05:06.373Z
First this problem should be solved for a=0 and for b=0, until then there is no point in attacking the general problem.
domotorp
CC BY-SA 3.0
2013-11-09T10:19:21.913Z
Ok, a=0 is pretty easy to 2-approximate, but I don't know about b=0.
domotorp
<approximation-algorithms><optimization><computational-geometry>
Tiling a rectangle with weighted cells (min-max problem)
SaSa
# Tiling a rectangle with weighted cells (min-max problem)

(Asked by: username_0 on 2013-11-07)

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](https://mathoverflow.net/questions/141797/tiling-a-rectangle-with-weighted-cells-min-max-problem?noredirect=1#comment375379_141797).

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

**Tags:** approximation-algorithms, optimization, computational-geometry
> **Comments:**
> **username_1**: First this problem should be solved for a=0 and for b=0, until then there is no point in attacking the general problem.  
> **username_1**: Ok, a=0 is pretty easy to 2-approximate, but I don't know about b=0.  

---

## 0 answers

