Timeline for reference that minimum makespan on identical machines is NP-hard?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2021 at 17:52 | comment | added | Inuyasha Yagami | 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. | |
| Oct 25, 2021 at 12:55 | comment | added | dpdp | @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 | |
| Oct 25, 2021 at 12:09 | comment | added | Inuyasha Yagami | You can simply mention that reduction follows from Partition problem. How about that? | |
| Oct 25, 2021 at 11:35 | history | asked | dpdp | CC BY-SA 4.0 |