The problem:

I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times q}$ satisfying

1) $1 \leq p,q \leq m$

2) $A(1,1) = A(p,q) = 1$ and $A(i,j) = 0$ otherwise.

I want to find the smallest $n$ and an $(0,1)$-matrix $B_{n\times n}$ so that $B$ contains every matrix in $\mathcal{M}$. We define that $B$ contains a matrix $A$ if and only if there exists $1 \leq i,j \leq n$ so that $A_{p \times q} = B(\{i,\dots,i+p-1\}, \{j,\dots,j+q-1\})$. Informally speaking, we want the template $B$ contains every patterns in $\mathcal{M}$.

The problem looks like a 2D extension of the shortest superstring problem. However, the patterns are very restricted.

The questions:

1) Is this problem NP-hard or not?

2) Could we come up with an approximation algorithm with performance guarantees?

3) If both of questions one and two are hard to answer, what are good heuristics for designing the template $B$?

4) Suppose $\mathcal{M}$ is a given set of matrices without constraints, can we still solve it with an approximation algorithm?

  • $\begingroup$ Probably I misunderstand the problem, but I wonder why $n=\max\{\max\{p,q\} \mid A_{p\times q} \in \mathcal{M}\}$ doesn't work? $\endgroup$ – Yoshio Okamoto Mar 21 '13 at 14:20
  • $\begingroup$ @Yoshio Every matrix $A$ in $\mathcal{M}$ needs to be an EXACT submatrix of $B$. $\endgroup$ – Peng Du Mar 22 '13 at 7:36

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.