13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are you looking for an upperbound for each $t_n$? how tight do you want the upperbound to be? It is lilely that very tight upperbounds do not exist (in reasonable time), but maybe something like a maximum 50% gap does exist. This problem also shows up in optimization problems with discrete time quite alot. So you could look there as well. $\endgroup$
    – zen
    Jun 24, 2017 at 0:18
  • $\begingroup$ @zen I'm looking the the maximum stretch under the assumption that we can choose $t_n$ as we need. $t_n$ themselves don't have to be contained in the solution. $\endgroup$
    – Zyx
    Jun 24, 2017 at 7:29

1 Answer 1

3
+50
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Sorry for the ambiguity - shorter strings can definitely 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. $\endgroup$
    – Zyx
    Jun 24, 2017 at 8:24
  • $\begingroup$ Ok, I'll take it into account a bit later. $\endgroup$
    – Smylic
    Jun 24, 2017 at 11:48
  • $\begingroup$ @ZyTelevan I've extended my answer. $\endgroup$
    – Smylic
    Jun 24, 2017 at 23:35
  • $\begingroup$ While this doesn't answer the main question, it is still very useful. Thank you a lot! $\endgroup$
    – Zyx
    Jun 25, 2017 at 10:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .