I wonder what relations are between the knapsack problem, the bin packing problem and the set packing problem?

From their mathematical formulations, I don't see the first two belong to the third one i.e. the set packing problem, although I feel the third one sounds more general than the other two.

Or under what conditions there are some conversions between each other?


  • 1
    $\begingroup$ Aren't these all NP-complete? All NP-complete problems can be converted to eachother in polynomial time. See wp:Karp's_21_NP-complete_problems. $\endgroup$ – Realz Slaw Oct 31 '12 at 14:44
  • $\begingroup$ @Realz_Slaw: Thanks! Your point from polynomial reduction is correct. I was asking about relations and conversions at the level of problem formulations. Or are these two points of view the same? $\endgroup$ – Tim Oct 31 '12 at 14:47
  • $\begingroup$ Well you could be asking for a more direct conversion, and/or a human explanation about their relationship, as the reductions given for one NP-complete problem to another can be multi-step (conversion to multiple intermediate problems) and lose a lot of easily "explainable" information. Or you could be asking something I simply don't understand. $\endgroup$ – Realz Slaw Oct 31 '12 at 14:53
  • $\begingroup$ Are you asking about "one-one reduction"? $\endgroup$ – Reza Feb 1 '13 at 3:29
  • $\begingroup$ @Reza: it can be that or any others. $\endgroup$ – Tim Feb 1 '13 at 3:38

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.