<p>Here's a poly-time dynamic-programming algorithm.</p>
<p><strong>Lemma 1.</strong> <em>The problem in the post has a poly-time dynamic-programming algorithm.</em></p>
<p><em>Proof sketch.</em> Fix an input <span class="math-container">$(\zeta, c)$</span> over time slots <span class="math-container">$\{1,2,\ldots, n\}$</span>.</p>
<p>For each <span class="math-container">$t, p\in \{0, 1,\ldots, n\}$</span>, define subproblem <span class="math-container">$M(t, p)$</span> as follows.  Consider the problem restricted to the first <span class="math-container">$t$</span> time slots.  (That is, the problem over time slots <span class="math-container">$\{1,2,\ldots, t\}$</span>, with <span class="math-container">$\zeta$</span> and <span class="math-container">$c$</span> restricted to those time slots.)  For this restricted problem, consider just those solutions that have total penalty <span class="math-container">$p$</span> and (if <span class="math-container">$t\ge 1$</span>) do use slot <span class="math-container">$t$</span>.  Define <span class="math-container">$M(t, p)$</span> to be the maximum, over all such solutions, of the capacity <span class="math-container">$C(t)$</span> achieved by that solution.  (Or <span class="math-container">$-\infty$</span> if there are no such solutions.)</p>
<p>The desired answer is <span class="math-container">$\min \{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$</span>.</p>
<p>Then <span class="math-container">$M(0, 0) = 0$</span> and <span class="math-container">$M(0, p) = -\infty$</span> for <span class="math-container">$p&gt;0$</span>.  For <span class="math-container">$t&gt;0$</span>,  the following recurrence relation holds.</p>
<p><span class="math-container">$M(t, p)$</span> is the maximum, over <span class="math-container">$s\in\{0,1,\ldots,t-1\}$</span>, of</p>
<p><span class="math-container">$$\begin{cases}
M(s, p-\lfloor(t-s-1)/2\rfloor) -c(t) + \sum_{i=s+1}^t \zeta(i)
&amp; \scriptsize\textit{ (if that quantity is well-defined and non-negative)} \\
-\infty &amp; \scriptsize\textit{ (otherwise). }
\end{cases}
$$</span>
Here's the intuition.  Consider the possible solutions for the first <span class="math-container">$t$</span> time slots that use slot <span class="math-container">$t$</span> and achieve total penalty <span class="math-container">$p$</span>.  Partition these solutions according to their last slot used, say, slot <span class="math-container">$s$</span>, before slot <span class="math-container">$t$</span>.  (Or <span class="math-container">$s=0$</span> if slot <span class="math-container">$t$</span> is the first slot used.)  Given <span class="math-container">$s$</span>, such a solution consists of some solution <span class="math-container">$S_s$</span> for slots <span class="math-container">$1,2,\ldots, s$</span> (with slot <span class="math-container">$s$</span> used if <span class="math-container">$s&gt;0$</span>), followed by unused slots <span class="math-container">$s+1,s+2,\ldots, t-1$</span>, followed by the used slot <span class="math-container">$t$</span>.</p>
<p>The penalty incurred for the size-<span class="math-container">$(t-s)$</span> block of unused slots <span class="math-container">$s+1,\ldots, t-1$</span> is <span class="math-container">$\lfloor (t-s)/2\rfloor$</span>.  So the cumulative penalty incurred by <span class="math-container">$S_s$</span> must be <span class="math-container">$p$</span> minus this.  The capacity <span class="math-container">$C(t)$</span> at time <span class="math-container">$t$</span> must be the capacity <span class="math-container">$C(s)$</span> achieved by <span class="math-container">$S_s$</span> at time <span class="math-container">$s$</span> plus the additional capacity added for unused slots <span class="math-container">$s+1,\ldots, t$</span>, minus <span class="math-container">$\zeta(t)$</span> for using slot <span class="math-container">$t$</span>.  So <span class="math-container">$C(t)$</span> will be maximized when <span class="math-container">$C(s)$</span> is maximized (over all solutions <span class="math-container">$S_s$</span> with appropriate penalty).  This is why the recurrence relation holds.</p>
<p>There are <span class="math-container">$O(n^2)$</span> subproblems, and for each the right-hand side of the recurrence can be evaluated in time <span class="math-container">$O(n)$</span> (with appropriate preprocessing), so this yields an <span class="math-container">$O(n^3)$</span>-time dynamic-programming algorithm. <span class="math-container">$~~\Box$</span>.</p>

CC BY-SA 4.0
2020-07-06T02:05:25.613Z
In the reccurrence relation, did you mean $-c(t)+\sum_{i=s+1}^{t}\zeta(i)$ instead of $-\zeta(t)+\sum_{i=s+1}^{t}c(i)$
zdm
CC BY-SA 4.0
2020-07-06T02:56:29.480Z
Yes, got them backwards.  Also had an off-by-one error.  Edited to fix them both.
Neal Young
CC BY-SA 4.0
2020-11-07T23:23:12.087Z
Hi. If we have two jobs instead of one and we have $\zeta_1$ and $\zeta_2$ and $c_1$ and $c_2$ for job 1 and job 2 respectively. If the two jobs cannot be scheduled at the same slot, can we still solve the problem using dynamic programming?
zdm
CC BY-SA 4.0
2020-06-26T21:18:41.103Z
2020-07-06T02:56:09.060Z
2020-07-06T02:56:09.060Z
Neal Young
<p>There are a single job, a machine and a set of <span class="math-container">$n$</span> slots. The machine has a capacity that increments by <span class="math-container">$\zeta(t)$</span> every slot <span class="math-container">$t=1,2,\ldots,n$</span>. Initially (before the first slot), the machine has 0 capacity i.e., the available capacity <span class="math-container">$C(t)$</span> at slot <span class="math-container">$t$</span> is <span class="math-container">$C(t):=\sum_{s\leq t}\zeta(s)$</span> (if the job was not scheduled at <span class="math-container">$t$</span> or before <span class="math-container">$t$</span>). If the job is scheduled at slot <span class="math-container">$t$</span>, then it will consume <span class="math-container">$c(t)$</span> units of the available capacity <span class="math-container">$C(t)$</span>. If the job is not scheduled for a period of <span class="math-container">$x$</span> <strong>consecutive</strong> slots, then a <strong>penalty</strong> of <span class="math-container">$\lfloor x/2\rfloor$</span> occurs.</p>
<p><strong>EDIT</strong></p>
<ul>
<li><p>We have to guarantee that <span class="math-container">$C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$</span> for all <span class="math-container">$t$</span> where <span class="math-container">$S\subseteq\{1,2,\ldots,t\}$</span> is the set of slots where the job was scheduled.</p>
</li>
<li><p>For the penalty: there is a penalty for every contiguous unused block.</p>
</li>
</ul>
<p>Here, is an example to illustrate the problem. Say <span class="math-container">$n=8$</span> and the job is scheduled at time <span class="math-container">$1$</span>, <span class="math-container">$4$</span>, and <span class="math-container">$8$</span>. Here, we have a penalty of <span class="math-container">$\lfloor{2/2}\rfloor=1$</span> between time <span class="math-container">$1$</span> and <span class="math-container">$4$</span> since the job is not scheduled for a period of 2 consecutive slots (<span class="math-container">$2$</span> and <span class="math-container">$3$</span>). Also, we have a penalty of <span class="math-container">$\lfloor{3/2}\rfloor=1$</span> between time <span class="math-container">$4$</span> and <span class="math-container">$8$</span> since the job is not scheduled for a period of 3 consecutive slots (<span class="math-container">$5$</span>, <span class="math-container">$6$</span> and <span class="math-container">$7$</span>). Thus, the objective here is <span class="math-container">$1+1$</span>.</p>
<p>Given <span class="math-container">$\zeta(t)$</span>, <span class="math-container">$c(t)$</span> for all <span class="math-container">$t=1,2,\ldots,n$</span>, the objective is to schedule the job during the <span class="math-container">$n$</span> slots in order to minimize the <strong>sum of penalties</strong> while respecting the capacity of machine in all scheduled slots.
Is this problem NP-hard?</p>
<p>I tried to reduce the knapsack problem to it but I did not succeed yet. Also, I tried to solve the problem in polynomial-time using dynamic programming but failed also due to the incremental capacity.</p>

CC BY-SA 4.0
2020-06-26T20:44:43.283Z
For (i) and (ii), yes, we have to guarante that $C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$ for all $t$. I don't get the difference between the last part of (iii) and (iv) but there is a penalty for every contiguous unused block. I will edit the question and give an example to illustrate my meaning.
zdm
CC BY-SA 4.0
2020-06-26T21:36:41.717Z
yes for every maximal contiguous block.
zdm
<ds.algorithms><np-hardness><dynamic-programming>
Minimizing the gaps with incremental capacity
zdm
# Minimizing the gaps with incremental capacity

(Asked by: username_0 on 2020-06-26)

There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 capacity i.e., the available capacity $C(t)$ at slot $t$ is $C(t):=\sum\_{s\leq t}\zeta(s)$ (if the job was not scheduled at $t$ or before $t$). If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the available capacity $C(t)$. If the job is not scheduled for a period of $x$ **consecutive** slots, then a **penalty** of $\lfloor x/2\rfloor$ occurs.

**EDIT**

* We have to guarantee that $C(t)=\sum\_{s\leq t}\zeta(s)-\sum\_{s\in S}c(s)\geq 0$ for all $t$ where $S\subseteq\{1,2,\ldots,t\}$ is the set of slots where the job was scheduled.
* For the penalty: there is a penalty for every contiguous unused block.

Here, is an example to illustrate the problem. Say $n=8$ and the job is scheduled at time $1$, $4$, and $8$. Here, we have a penalty of $\lfloor{2/2}\rfloor=1$ between time $1$ and $4$ since the job is not scheduled for a period of 2 consecutive slots ($2$ and $3$). Also, we have a penalty of $\lfloor{3/2}\rfloor=1$ between time $4$ and $8$ since the job is not scheduled for a period of 3 consecutive slots ($5$, $6$ and $7$). Thus, the objective here is $1+1$.

Given $\zeta(t)$, $c(t)$ for all $t=1,2,\ldots,n$, the objective is to schedule the job during the $n$ slots in order to minimize the **sum of penalties** while respecting the capacity of machine in all scheduled slots.
Is this problem NP-hard?

I tried to reduce the knapsack problem to it but I did not succeed yet. Also, I tried to solve the problem in polynomial-time using dynamic programming but failed also due to the incremental capacity.

**Tags:** ds.algorithms, np-hardness, dynamic-programming
> **Comments:**
> **username_0**: For (i) and (ii), yes, we have to guarante that $C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$ for all $t$. I don't get the difference between the last part of (iii) and (iv) but there is a penalty for every contiguous unused block. I will edit the question and give an example to illustrate my meaning.  
> **username_0**: yes for every maximal contiguous block.  

---

## 1 answers

### Answer by username_1 on 2020-06-26. Score: 3 | Accepted answer

Here's a poly-time dynamic-programming algorithm.

**Lemma 1.** *The problem in the post has a poly-time dynamic-programming algorithm.*

*Proof sketch.* Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$.

For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows. Consider the problem restricted to the first $t$ time slots. (That is, the problem over time slots $\{1,2,\ldots, t\}$, with $\zeta$ and $c$ restricted to those time slots.) For this restricted problem, consider just those solutions that have total penalty $p$ and (if $t\ge 1$) do use slot $t$. Define $M(t, p)$ to be the maximum, over all such solutions, of the capacity $C(t)$ achieved by that solution. (Or $-\infty$ if there are no such solutions.)

The desired answer is $\min \{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$.

Then $M(0, 0) = 0$ and $M(0, p) = -\infty$ for $p>0$. For $t>0$, the following recurrence relation holds.

$M(t, p)$ is the maximum, over $s\in\{0,1,\ldots,t-1\}$, of

$$\begin{cases}
M(s, p-\lfloor(t-s-1)/2\rfloor) -c(t) + \sum\_{i=s+1}^t \zeta(i)
& \scriptsize\textit{ (if that quantity is well-defined and non-negative)} \\
-\infty & \scriptsize\textit{ (otherwise). }
\end{cases}
$$
Here's the intuition. Consider the possible solutions for the first $t$ time slots that use slot $t$ and achieve total penalty $p$. Partition these solutions according to their last slot used, say, slot $s$, before slot $t$. (Or $s=0$ if slot $t$ is the first slot used.) Given $s$, such a solution consists of some solution $S\_s$ for slots $1,2,\ldots, s$ (with slot $s$ used if $s>0$), followed by unused slots $s+1,s+2,\ldots, t-1$, followed by the used slot $t$.

The penalty incurred for the size-$(t-s)$ block of unused slots $s+1,\ldots, t-1$ is $\lfloor (t-s)/2\rfloor$. So the cumulative penalty incurred by $S\_s$ must be $p$ minus this. The capacity $C(t)$ at time $t$ must be the capacity $C(s)$ achieved by $S\_s$ at time $s$ plus the additional capacity added for unused slots $s+1,\ldots, t$, minus $\zeta(t)$ for using slot $t$. So $C(t)$ will be maximized when $C(s)$ is maximized (over all solutions $S\_s$ with appropriate penalty). This is why the recurrence relation holds.

There are $O(n^2)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(n)$ (with appropriate preprocessing), so this yields an $O(n^3)$-time dynamic-programming algorithm. $~~\Box$.

> **Comments:**
> **username_0**: In the reccurrence relation, did you mean $-c(t)+\sum_{i=s+1}^{t}\zeta(i)$ instead of $-\zeta(t)+\sum_{i=s+1}^{t}c(i)$  
> **username_1**: Yes, got them backwards.  Also had an off-by-one error.  Edited to fix them both.  
> **username_0**: Hi. If we have two jobs instead of one and we have $\zeta_1$ and $\zeta_2$ and $c_1$ and $c_2$ for job 1 and job 2 respectively. If the two jobs cannot be scheduled at the same slot, can we still solve the problem using dynamic programming?  

---

