<p>Let the problem, $P_{overlapping}$, be the following. 
We have an $N_1 \times N_2$ grid. Each cell of the grid can have the
value either 0 or 1. Assume that we have $a \times b$ overlapping windows as
the subset of the $N_1 \times N_2$ grid where $a &lt; N_1$ and $b &lt; N_2$,
and we want to have at least $k$ of the cells in each window
have the value 1. We are interested in minimizing the number
of cells having the value 1 when $N_1 \times N_2$ grid is covered by
$a \times b$ overlapping windows having $k$ cells with the value 1 in each.</p>

<p>And, let the problem, $P_{non-overlapping}$, be the following.
We have an $N_1 \times N_2$ grid, and each cell of the grid can have the
value either 0 or 1 similar to the problem, $P_{overlapping}$.
But this time, assume that we have $a \times b$ non-overlapping windows as
the subset of the $N_1 \times N_2$ grid where $a &lt; N_1$ and $b &lt; N_2$,
and we want to have at least $k$ of the cells in each window
have the value 1. We are interested in minimizing the number
of cells having the value 1 when $N_1 \times N_2$ grid is covered by
$a \times b$ non-overlapping windows having $k$ cells with the value 1 in each.</p>

<p>For an $N \times N$ grid, $\left \lfloor \frac{N}{a} \right \rfloor \times 
\left \lfloor \frac{N}{b} \right \rfloor \times
k$ is the lower bound for
$P_{non-overlapping}$.
In order to find optimal solutions for the problem $P_{overlapping}$, I used the following Integer Linear Programming formulation:</p>

<p>$
\begin{align}
\label{eqnew:01}
\mbox{Minimize: } &amp;{\displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} x_{ij}}   &amp;;&amp;  x_{ij} \in \{0,1\}   \notag \\
\mbox{Subject To: } &amp; {\displaystyle  \sum_{i=m}^{m+a-1} \ \sum_{j=n}^{n+b-1} x_{ij} \ge k}  &amp;;&amp;     \forall{m}, \ 1 \le m \le N_1-a+1 \notag \\
                    &amp;          &amp;,&amp;   \forall{n}, \ 1 \le n \le N_2-b+1
\end{align}

$</p>

<p>And using GLPK linear programming solver, and solving the problem for some $N \times N$ grids with $a \times b (12 \times 9)$ overlapping windows for $k=2$, 
I got some results for
optimum solutions for $P_{overlapping}$. Interestingly, when
I used  the lower bound for the problem $P_{non-overlapping}$,
$N \times N$ grid, $\left \lfloor \frac{N}{12} \right \rfloor \times 
\left \lfloor \frac{N}{9} \right \rfloor \times
2$ for $k=2$; solutions for both problems are the same as seen in the following graph  </p>

<p><a href="http://www.cs.utsa.edu/~btas/lowerBound12x9.png" rel="nofollow">comparison of the problems</a></p>

<p>And, finally, my question is the following. 
Why are these two different problems have the same solutions
for $k=2$? How about for $k$ values other than 2?
Is this reasonable theoretically?</p>

<p>Many thanks for your time, fellas.</p>

<p>Baris</p>

CC BY-SA 3.0
2011-12-02T06:54:50.867Z
In other words, you want to **assign** values to entries in the matrix to satisfy the constraints on the subrectangles ? that was not clear in your question. And notice that your "lower bound" which comes from placing 1s in an even pattern is also a valid solution for the overlapping case if I understand the problem correctly.
Suresh Venkat
CC BY-SA 3.0
2011-12-02T19:00:06.083Z
Yes, we are assigning values to entries in the matrix to satisfy the constraints on the subrectangles. Why is the solution for the non-overlapping subrectangles case also
Baris
CC BY-SA 3.0
2011-12-02T19:08:24.930Z
Yes, we are assigning values to entries in the matrix to satisfy the constraints on the subrectangles. Why is the solution for the non-overlapping subrectangles case also valid for the overlapping subrectangles case? Is this provable? Shouldn't the overlapping case have more number of entries assigned to the matrix compared to the non-overlapping case? ("I'm using floor for the "lower bound" computation")
Baris
<lower-bounds><optimization><linear-programming>
covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each
Baris
# covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each

(Asked by: username_0 on 2011-12-02)

Let the problem, $P\_{overlapping}$, be the following.
We have an $N\_1 \times N\_2$ grid. Each cell of the grid can have the
value either 0 or 1. Assume that we have $a \times b$ overlapping windows as
the subset of the $N\_1 \times N\_2$ grid where $a < N\_1$ and $b < N\_2$,
and we want to have at least $k$ of the cells in each window
have the value 1. We are interested in minimizing the number
of cells having the value 1 when $N\_1 \times N\_2$ grid is covered by
$a \times b$ overlapping windows having $k$ cells with the value 1 in each.

And, let the problem, $P\_{non-overlapping}$, be the following.
We have an $N\_1 \times N\_2$ grid, and each cell of the grid can have the
value either 0 or 1 similar to the problem, $P\_{overlapping}$.
But this time, assume that we have $a \times b$ non-overlapping windows as
the subset of the $N\_1 \times N\_2$ grid where $a < N\_1$ and $b < N\_2$,
and we want to have at least $k$ of the cells in each window
have the value 1. We are interested in minimizing the number
of cells having the value 1 when $N\_1 \times N\_2$ grid is covered by
$a \times b$ non-overlapping windows having $k$ cells with the value 1 in each.

For an $N \times N$ grid, $\left \lfloor \frac{N}{a} \right \rfloor \times
\left \lfloor \frac{N}{b} \right \rfloor \times
k$ is the lower bound for
$P\_{non-overlapping}$.
In order to find optimal solutions for the problem $P\_{overlapping}$, I used the following Integer Linear Programming formulation:

$
\begin{align}
\label{eqnew:01}
\mbox{Minimize: } &{\displaystyle \sum\_{i=1}^{N\_1}\sum\_{j=1}^{N\_2} x\_{ij}} &;& x\_{ij} \in \{0,1\} \notag \\
\mbox{Subject To: } & {\displaystyle \sum\_{i=m}^{m+a-1} \ \sum\_{j=n}^{n+b-1} x\_{ij} \ge k} &;& \forall{m}, \ 1 \le m \le N\_1-a+1 \notag \\
& &,& \forall{n}, \ 1 \le n \le N\_2-b+1
\end{align}
$

And using GLPK linear programming solver, and solving the problem for some $N \times N$ grids with $a \times b (12 \times 9)$ overlapping windows for $k=2$,
I got some results for
optimum solutions for $P\_{overlapping}$. Interestingly, when
I used the lower bound for the problem $P\_{non-overlapping}$,
$N \times N$ grid, $\left \lfloor \frac{N}{12} \right \rfloor \times
\left \lfloor \frac{N}{9} \right \rfloor \times
2$ for $k=2$; solutions for both problems are the same as seen in the following graph

[comparison of the problems](http://www.cs.utsa.edu/~btas/lowerBound12x9.png)

And, finally, my question is the following.
Why are these two different problems have the same solutions
for $k=2$? How about for $k$ values other than 2?
Is this reasonable theoretically?

Many thanks for your time, fellas.

Baris

**Tags:** lower-bounds, optimization, linear-programming
> **Comments:**
> **username_1**: In other words, you want to **assign** values to entries in the matrix to satisfy the constraints on the subrectangles ? that was not clear in your question. And notice that your "lower bound" which comes from placing 1s in an even pattern is also a valid solution for the overlapping case if I understand the problem correctly.  
> **username_0**: Yes, we are assigning values to entries in the matrix to satisfy the constraints on the subrectangles. Why is the solution for the non-overlapping subrectangles case also  
> **username_0**: Yes, we are assigning values to entries in the matrix to satisfy the constraints on the subrectangles. Why is the solution for the non-overlapping subrectangles case also valid for the overlapping subrectangles case? Is this provable? Shouldn't the overlapping case have more number of entries assigned to the matrix compared to the non-overlapping case? ("I'm using floor for the "lower bound" computation")  

---

## 0 answers

