Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

Thanks!

share|improve this question
1  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.