What is the name of this class of (combinatorial?) problems?

Question

Judging from the number of similar questions, I've found myself in a rather common situation: I've come up with a problem, encountered a dead end and am now searching for the name of the problem in order to learn more about it.

An example of the problem as follows:
Suppose we have a number of strings of ones and zeroes. For example:
$s_1: \fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{0}$
$s_2: \fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{0}\fbox{0}$
$s_3: \fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{0}\fbox{0}$
Now we construct a new string $H$ by horizontally shifting each sequence $s_n$ by some amount $t_n$ and applying logical disjunction to the columns. What is the longest possible sequence of consecutive ones in the resulting string, if we're allowed to choose $t_n$? By exhaustive search, a solution to this particular problem would be 5, which is given by $t_1=2$; $t_2=2$; $t_3=0$ :
$s_1: \phantom{0000}\fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{0}$
$s_2: \phantom{0000}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{0}\fbox{0}$
$s_3: \fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{0}\fbox{0}$
$H: \fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0}\fbox{0}\fbox{0}\fbox{0}$
Clarification: Shorter strings can extend past the longer ones, as long as the final string has no gaps. In principle, if all strings contained only $1$'s then the maximum stretch would be just $\sum_{i=1}^{n}{\lvert s_i \rvert}$, where $\lvert s_i \rvert$ is the length of $i$-th string.

The closest I could find is the Restricted Strip Covering problem, which is a special case of Geometric Set Covering, but it's not quite what I'm looking for.

---

Progress: The problem can be stated in terms of discrete job scheduling problem:
Suppose we have a number of employees who can work within a certain time span. Within that time span they may take certain gaps for leisure. Given a set of such employees, what is the maximum stretch of time in which at least one employee is working? The distinction between this problem and job-scheduling problem is important though - finding the optimal values for $t_n$ is NP-Hard, but maybe it's possible to calculate the maximum time without calculating $t_n$ in polynomial time.

Answer 1

I wouldn't tell you a name of such problem even if it exists, but I will show that the problem about maximum stretch of time is NP-hard. We can polynomially reduce SAT problem to the desired one in the following way.

Firstly I use an assumption that shoter string cannot come ouf of borders of the lonest one.

Given a formula $F$ of $m$ disjunctions on variables $x_1, x_2, \ldots, x_n$, we build the following set of strings. For each literal $x_1, \overline{x_1}, x_2, \ldots, \overline{x_n}$ we create a string of length $2m + 2n$ as follows:

• symbol at position $2i$ for $1 \le i \le m$ corresponds to the entry of corresponding literal into $i$th disjunction, i. e. is $1$ iff literal appears in $i$th disjunction;
• symbol at position $(2m + 2j - 1)$ for $1 \le j \le n$ is $1$ iff the string corresponds to either $x_j$ or $\overline{x_j};$
• all other symbols are $0$s.

One more string of length $2m + 2n + 1$ has $1$ at each odd position. It is easy to see that stretch of time is $2m + 2n + 1$ if and only if $F$ is satisfiable, because each even position $(2m + 2j)$ requires at least one of string corresponding to $x_j$ and $\overline{x_j}$ to be shifted by $1$ (i. e. requires this literal to be false), while each position $2i$ is a disjunction that requires at least one of srings corresponding to the literals of this disjunction to be shifted by $0$ (i. e. requires at least one true literal). Thus the problem about maximum stretch of time is NP-hard.

---

EDIT. Now we need to allow arbitrary shift of all string. For that purpose we add $4n(n + m)$ more symbols to each string. For $i$th string, $1 \le i \le 2n$ these symbols are $0$s except positions between $2i(n + m) + 1$ and $2(i + 1)(n + m)$, inclusive, where only $1$s are placed. The last string has $1$s at positions $2i(n + m) + 1$ for all $2 \le i \le 2n + 1$ and $0$s at all other positions.

It is not hard to see that we can get stretch of time $2(2n + 1)(n + m) + 1$ if and only if $F$ is satisfiable. And shifts of all strings should be $0$ or $1$ to make such stretch of time.

---

Example. Let $$F = (x_1 \lor x_2) \land (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor x_2) \land (\overline{x_1} \lor \overline{x_2}).$$

Then corresponding set of strings is the following:

$x_1\colon s_1 =$ 01010000 1000 111111111111 000000000000 000000000000 000000000000
$\overline{x_1}\colon s_2 =$ 00000101 1000 000000000000 111111111111 000000000000 000000000000
$x_2\colon s_3 =$ 01000100 0010 000000000000 000000000000 111111111111 000000000000
$\overline{x_2}\colon s_4 =$ 00010001 0010 000000000000 000000000000 000000000000 111111111111
and $s_5 =$ 10101010 1010 100000000000 100000000000 100000000000 100000000000 1

It is not hard to see that we cannot get stretch of time $61$ therefore $F$ is not satisfiable.