Cover 2 by n binary matrix with submatrices of minimum total size

Question

This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the size of the submatrices (we consider the size of a matrix the product of its rows and columns) and we use no more than $L$ submatrices. For example, if $A$ is $$ 1 \quad 1 \quad 0 \quad 0 \quad 1 \quad 1\\ 0 \quad 1 \quad 1 \quad 0 \quad 0 \quad 0 $$ and $L = 2$, the optimal solution would be covering $A$ with 2 submatrices of sizes $2 \times 3$ and $1 \times 2$: $$ x \quad x \quad x \quad 0 \quad x \quad x\\ x \quad x \quad x \quad 0 \quad 0 \quad 0 $$ in this case the output of an algorithm solving this problem should be $8$ (the sum of the sizes of the submatrices: $2\cdot 3 + 1 \cdot 2$), and $2$ (which means that we used 2 submatrices).

I've come up with a partial solution using dynamic programming, but it is so long that I doubt it is correct. In summary, suppose that we start to analyze the input array from the first column until the $k$-th column. Let $C_{OPT}(k)$ and $M_{OPT}(k)$ be the optimal solutions at the $k$-th column. If $M_{OPT} = L$ then we have two analyze whether the previous submatrix used covers the $(k-1)$-th column or not, and then observe how many 1s there are at the $k$-th column. Based on that, the recursive relationships between $C_{OPT}(k)$ and $C_{OPT}(k-1)$ can be written. However, I haven't figured out yet how to analyze the case where $M_{OPT} < L$.

Is my approach correct so far? Or is there a better way to solve this problem?

Answer 1

It looks like you are in the right direction.

In order to establish recurrence relations, we need more subproblems. The final solution is probably even longer than what you have done!

Let $A$ be the given binary array (the leftmost column of $A$ is the first column). For each pairs of numbers $(k, s)$, where $1\le k\le n$, $0\le s\le L$,

• Let $N(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that neither of $A[0][k]$ and $A[1][k]$ $A[1][k]$ is covered.
• let $U(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A[1][k]$ is not covered.
• let $L(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A[0][k]$ is not covered.
• let $B_1(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A[0][k]$ and $A[1][k]$ are covered by the same submatrix.
• let $B_2(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A[0][k]$ and $A[1][k]$ are covered by different submatrices.

When $k$ or $s$ is out of bounds, consider all costs defined above as infinity.

The differences among $N(k,s), U(k,s), L(k,s), B_1(k,s)$ and $B_2(k,s)$ are how the $k$-th column is covered.

The recurrence relations are

$$N(k, s) = \begin{cases} \infty &\mbox{if }A[0][k]=1 \mbox{ or } A[1][k]=1 \\ \min(N(k-1,s), U(k-1,s), L(k-1,s), B_1(k-1,s), B_2(k-1, s))&\mbox{otherwise} \end{cases}$$

$$U(k, s) = \begin{cases} \infty &\mbox{if }A[1][k]=1 \\ 1 + \min(N(k-1,s-1), U(k-1,s), L(k-1,s-1), B_1(k-1,s), B_2(k, s-1))&\mbox{otherwise} \end{cases}$$

$$L(k, s) = \begin{cases} \infty &\mbox{if }A[0][k]=1 \\ 1+\min(N(k-1,s-1), U(k-1,s-1), L(k-1,s), B_1(k-1,s), B_2(k, s-1))&\mbox{otherwise} \end{cases}$$

$$B_1(k, s) = 2 + \min(N(k-1,s-2), U(k-1,s-1), L(k-1,s-1), B_1(k-1,s), B_2(k, s-2))$$

$$B_2(k, s) = 2 + \min(N(k-1,s-1), U(k-1,s-1), L(k-1,s-1), B_1(k-1,s-1), B_2(k-1, s))$$

The initial values, $N(1,s)$, $U(1,s)$, $L(1,s)$, $B_1(1,s)$, $B_2(1,s)$ can be determined easily.

The final answer is $N(n+1, L)$.