I need to cite a reference that the minimum makespan problem on ($>2$) identical machines is NP-hard. I've seen Garey and Johnson cited as a reference, but it I'm not sure which of the problems is exactly equivalent to this one.

  • $\begingroup$ You can simply mention that reduction follows from Partition problem. How about that? $\endgroup$ Oct 25 at 12:09
  • $\begingroup$ @InuyashaYagami thanks! Since $m>2$ I guess it is actually multiway number partitioning and the references I found for that just point back to the original work on job scheduling... I guess they are referring to SS8 from Garey and Johnson, but not completely sure $\endgroup$
    – dpdp
    Oct 25 at 12:55
  • $\begingroup$ All such hardness proofs follow from the subset sum problem. The NP-completeness proof of subset sum problem is given in CLRS using a reduction from 3SAT. Then, the reduction to partition problem with 2 sets and further to multiway number partitioning follows from there. $\endgroup$ Oct 25 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.