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$
    – ZyTelevan
    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$
    – ZyTelevan
    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$
    – ZyTelevan
    Jun 25, 2017 at 10:42

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.