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.

  • $\begingroup$ 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$. $\endgroup$
    – Highheath
    Apr 12, 2022 at 2:07
  • $\begingroup$ @Highheath thanks. Would it be possible to provide additional hints? $\endgroup$
    – user3472
    Apr 12, 2022 at 2:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.