# scheduling with profits and deadlines clrs

The following problem is on page 1104 of the CLRS textbook:

I was wondering how to show that the problem is NP-hard (i.e. part b)?

Like subset-sum, this problem is weakly NP-complete; it has a pseudo-polynomial time dynamic programming algorithm.

Let's say I choose to reduce via subset sum. We want to find the schedule that returns a profit of at least $$k$$ for the decision version. In subset sum, we have a set of values $$v_1,\cdots, v_n$$, a target $$W$$, and we want to find a subset $$S\subseteq \{1,\cdots, n\}$$ so that $$\sum_{i\in S} v_i = W$$.

It might be useful to prove that a special case of this problem is NP-complete. For the given problem, maybe I can choose the profits to be $$v_i$$? Then the target can be $$k$$, where k is the parameter in the decision version of this problem.

• You're on the right track - there is a reduction from SUBSET SUM, and it involves setting each $p_j$ equal to $v_j$ and the target equal to $W$. This way, you only reach your target if there's a subset with sum at least $W$. Your task now is to find out how to set the $d_j$'s and $t_j$'s such that $W$ is the highest obtainable score. This way the only way to reach the target is if a subset adds to exactly $W$. Apr 12, 2022 at 2:07
• @Highheath thanks. Would it be possible to provide additional hints? Apr 12, 2022 at 2:12