MSSP-I is strongly NP-hard

[YouJiacheng]

Note: MSSP in following screen shot is actually MSSP-I

Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). The Multiple Subset Sum Problem. SIAM Journal on Optimization, 11(2), 308–319. doi:10.1137/s1052623498348481

How can a strongly NP-hard problem be solved in pseudo-polynomial time?

[YouJiacheng]

In [34](Cited in GreenMIM paper) H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack problems. Springer, 2004:

[YouJiacheng]

BTW, since the number of groups is not given and each window is required to be in one group. The problem is more similar to the Bin Packing Problem instead of the Multiple Subset Sum Problem.

[LayneH]

Hi,

I agree that the pointed sentence is not rigorous enough. What we tried to put forth there is that there exist multiple polynomial-time approximation schemes for MSSP-I. We will fix this part and make it more clear in the updated version.
Thanks for the note and for referring to Bin Packing Problem.