Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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. – Realz Slaw Oct 31 '12 at 14:44
@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? – Tim Oct 31 '12 at 14:47
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. – Realz Slaw Oct 31 '12 at 14:53
Are you asking about "one-one reduction"? – Reza Feb 1 '13 at 3:29
@Reza: it can be that or any others. – Tim Feb 1 '13 at 3:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.