2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Can you explain what is $C_{OPT}(k)$ and $M_{OPT}(k)$? Is $C_{OPT}(k)$ a number? Is $M_{OPT}(k)$ a map? $\endgroup$
    – John L.
    Nov 7, 2021 at 18:06
  • $\begingroup$ @JohnL.: $C_{OPT}(k)$ and $M_{OPT}(k)$ are both numbers. For the input array up to the $k$-th column, $C_{OPT}(k)$ is the optimal cost and $M_{OPT}(k)$ is the optimal number of submatrices that we have used. $\endgroup$
    – Rob32409
    Nov 7, 2021 at 18:44

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
4
  • $\begingroup$ Had there are more than 2 rows in the given array, we may compute the recurrence relations by code. $\endgroup$
    – John L.
    Nov 8, 2021 at 15:27
  • $\begingroup$ Thanks. I actually came up with an answer very similar to yours. How can the correctness of such algorithm be proved? I know that we probably have to use induction, but since there are many cases to consider is there a more compact way to prove this? $\endgroup$
    – Rob32409
    Nov 8, 2021 at 17:39
  • $\begingroup$ $N(n+1,L)$, where $n+1\gt n$ is out of bounds, is not considered as infinity. $\endgroup$
    – John L.
    Nov 8, 2021 at 17:39
  • $\begingroup$ Well, had we written code/algorithm to compute the recurrence relations, would that be the base for a proof? Anyway, a rigorous proof of some exact implementation might not be insightful. What is more useful is the idea of more refined subproblems. $\endgroup$
    – John L.
    Nov 8, 2021 at 17:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.