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.
3
-
$\begingroup$ You can simply mention that reduction follows from Partition problem. How about that? $\endgroup$– Inuyasha YagamiCommented Oct 25, 2021 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$– dpdpCommented Oct 25, 2021 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$– Inuyasha YagamiCommented Oct 25, 2021 at 17:52
Add a comment
|