Return to Answer

My previous construction of matrix $h$ is wrong; I've editted it.

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose $k_i$ larger one in the two numbers of appearances of literals $x_i$ and $\overline{x_i}$.

• For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
• For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_i-j)=X$.
• For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
• All the other entries are 0.

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively.

• For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
• For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$.
• For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
• All the other entries are 0.

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose each variable $x_i$ appears $k_i$ times in the formula.

• "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the "color" $x_i(j)$, and $\bar{v}_i(j)$ with $\overline{x_i}(j)$.
• "Clause" vertices $w_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w_{i'}(j')$ with the color $x_i(j)$ (or $\overline{x_i}(j)$) if $\overline{x_i}$ (or $x_i$, resp.) is the $j'$-th literal of clause $\phi_{i'}$, and it's the $j$-th clause containing the variable $x_i$.
• "Cut" vertices $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$. Color them with distinct colors different from above.

For instance, from the 3CNF $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_4)$ the following graph is constructed (The edge directions are from left to right).

So what is the relation between $G$ and OP's problem? What we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and each part is mapped to a part of consecutive columns (time slots). A maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.

The cut vertices separate $G$ into $n+k$ parts. The last $k$ parts, corresponding to the $k$ clauses, are easy. For the $(n+i')$-th part, there is only one column, and the entries in the rows corresponding to the three literals are $1$ while others are $0$.

Now consider the $i$-th part corresponding to the assignment of $x_i$. In the $i$-th part there are $2k_i+3$ columns (labeled from $-1$ to $2k_i+1$), and we add two colors $x_i(0)$ and $\overline{x_i}(k_i+1)$ which will only be used here. The non-zero entries are:

• $h(x_i(0))=\{X,Z,Y,0,0,\ldots,0\}$, $h(\overline{x_i}(k_i+1))=\{0,0,\ldots,0,Y,Z,X\}$.
• $h(x_i(k_i),2k_i)=Y$, $h(\overline{x_i}(1),0)=Y$.
• $h(x_i(j),2j)=h(x_i(j),2j+1)=Y$, $\forall 1\leq j\leq k_i-1$.
• $h(\overline{x_i}(j),2j-3)=h(\overline{x_i}(j),2j-2)=Y$, $\forall 2\leq j\leq k_i$.

For example, if $k_i=3$ the corresponding submatrix is $$ \begin{array}{rccccccccc} x_i(0)\, & X & Z & Y & 0 & 0 & 0 & 0 & 0 & 0\\ x_i(1)\, & 0 & 0 & 0 & Y & Y & 0 & 0 & 0 & 0\\ x_i(2)\, & 0 & 0 & 0 & 0 & 0 & Y & Y & 0 & 0\\ x_i(3)\, & 0 & 0 & 0 & 0 & 0 & 0 & 0 & Y & 0\\ \overline{x_i}(1)\, & 0 & Y & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \overline{x_i}(2)\, & 0 & 0 & Y & Y & 0 & 0 & 0 & 0 & 0\\ \overline{x_i}(3)\, & 0 & 0 & 0 & 0 & Y & Y & 0 & 0 & 0\\ \overline{x_i}(4)\, & 0 & 0 & 0 & 0 & 0 & 0 & Y & Z & X \end{array} $$

Besides, for each cut vertex $s_1,\ldots,s_{n+k-1}$, there is a corresponding column with only one $X$ at the corresponding row. The values $X,Y,Z$ satisfy $1\ll Z\ll Y\ll X$. The ratios $Z/1, Y/Z, X/Y$ can be large powers of $k$ and $n$. Finally we glue all parts together in order.

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+n+k-1)X+\sum_i 2k_iY+nZ+k$.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+n+k-1)$ columns in $h$ containing (actually only one) $X$, they should all be covered. Next we claim in each assignment part of $x_i$, the maximum value is $2k_iY+Z$. It is done by the following simple observations:

• For two consecutive $Y$'s in a row, if one of them is chosen, it won't get worse if we also choose the other one.
• For the consecutive $ZY$ or $YZ$ in a row, if the $Y$ is chosen then the $Z$ must be chosen (because of the consecutiveness and the $X$ nearby is already chosen), and if the $Z$ is chosen it won't get worse if we also choose the $Y$.

Therefore, in the optimal scheduling we can assume for each conseutive $YY$, $YZ$ or $ZY$ in a row, either both of them are selceted or neither. It is easy to check that in this case, we either assign all the slots to $x_i$ or all to $\overline{x_i}$, which both give rise to a value of $2k_iY+Z$.

Now this can be regarded as an assignment, and since a person could only have consecutive blocks, if $x_i$ is chosen then it cannot be used in the clause part. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.

My previous construction of matrix $h$ is wrong; I've editted it.

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose $k_i$ larger one in the two numbers of appearances of literals $x_i$ and $\overline{x_i}$.

• "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the "color" $x_i(j)$, and $\bar{v}_i(j)$ with $\overline{x_i}(j)$.
• "Clause" vertices $w_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w_{i'}(j')$ with the color $x_i(j)$ (or $\overline{x_i}(j)$) if $\overline{x_i}$ (or $x_i$, resp.) is the $j'$-th literal of clause $\phi_{i'}$, and it's the $j$-th clause containing this literal.
• "Cut" vertices $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$. Color them with distinct colors different from above.

For instance, from the 3CNF $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$ the following graph is constructed (The edge directions are from left to right).

So what is the relation between $G$ and OP's problem? Intuitively what we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and the edges are mapped to consecutive columns (time slots). Therefore a maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.

Our matrix $h$ have $2n+1+\sum_i 2k_i+k$ columns, with indices starting from $0$. In the following constrcution $X$ an $Y$ are two values satisfy $1\ll X\ll Y$. The ratios $X/1, Y/X$ can be large powers of $k$ and $n$. Let $K_i=2i+2\sum_{j=1}^i k_i$.

• For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
• For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_i-j)=X$.
• For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
• All the other entries are 0.

For example, for the above example graph the corresponding matrix is

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum_i k_iX+k$.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+1)$ columns in $h$ containing $Y$, they should all be covered. For the column $K_i+k_i+1$ which has two choices of $Y$, suppose the scheduling assigns it to $s_i$. Since column $K_i$ must be assigned to $s_i$, by the consecutiveness we have to lose the columns $K_i+1$ to $K_i+k_i$. Same things happen if the scheduling assign the column $K_i+k_i+1$ to $s_{i+1}$.

Therefore, in order to have the value $\sum_i k_iX$, we must select all the rest available $X$'s in the matrix, which corresponds to an assignment on variables. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+n+k-1)$ columns in $h$ containing (actually only one) $X$, they should all be covered. Next we claim in each assignment part of $x_i$, the maximum value is 2k_iY+Z. It is done by the following simple observations:

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+n+k-1)$ columns in $h$ containing (actually only one) $X$, they should all be covered. Next we claim in each assignment part of $x_i$, the maximum value is $2k_iY+Z$. It is done by the following simple observations: