-1
$\begingroup$

This question already has an answer here:

This is my first time with reductions and I can't figure out how to do them. I have read the few standard examples that are given in the standard books.

For example, given $n$ numbers $\{ 0 < s_i <1 , \text{ for }i = 1,..,n \}$ one wants to minimize the number of number of bins required to pack them if each bin can have at most a sum of $1$.

  • How does one show the NP-completeness of the above by reducing it from the SUBSET-SUM problem?

  • I also saw this related question here which remains unanswered, Relaxed Bin Packing Problem

Can someone help?


Is there some reference (on the web?) which shows a lot of such reductions - I think reading them will help me understand the kind of thinking that is required!

$\endgroup$

marked as duplicate by D.W., Raphael Sep 10 '14 at 8:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Welcome! You may be interested in our reference questions. We expect questions like your to contain answers to the questions "What have you tried? Where did you get stuck?". $\endgroup$ – Raphael Sep 10 '14 at 8:49
1
$\begingroup$

To prove that a problem is NP-complete you need to find the decision version of your optimization problem. The answer to the decision problem is yes/no.

Once you state the decision problem, you need to prove that your problem is NP. It means that, given a certificate (an optimal solution) you can verify the feasibility of the solution in polynomial time.

Then you need to prove the NP-hardness, which means that you must reduce an NP-hard problem to your problem. The reduction is in fact, converting every instance of that NP-hard problem, to an instance of your own problem in polynomial time so that, if there is a polynomial algorithm for your problem, it can decide that problem in polynomial time.

In this document, there is the np-completeness proof of bin packing: http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin_packing.pdf

In famous text books you can find the np-completeness proof of: TSP, Hamiltonian path, longest path, set cover, vertex cover, clique and ....

In this document there are a number of good practices: http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/111-137.pdf

Edit. For the relaxed bin packing, I should say that, sometimes you can relax/ignore some of the conditions in your problem. For example, in bin packing problem, one strict condition is that you should put each item into one bin and you cannot split one item into multiple bins. One may allow each item to be split into multiple bins (now this problem can be solved in polynomial time) which is called the relaxed version of the problem. Sometimes, relaxing one condition (such as integrality of solution) and rounding the obtained solution can give us approximation algorithms. I suggest you to search for relaxation in integer programming for more information.

$\endgroup$
  • $\begingroup$ Thanks for the links! Will look into them! What do you think of that "relaxed bin packing" question lying idle on this site - is that the same kind of thing? $\endgroup$ – user6818 Sep 10 '14 at 2:18
  • $\begingroup$ Look at the edit. Relaxation is one approach to solve some problems and achieve an approximation ratio. $\endgroup$ – orezvani Sep 10 '14 at 2:44
  • $\begingroup$ I didn't get you - are you saying that the linked question is in P? $\endgroup$ – user6818 Sep 10 '14 at 3:40
  • $\begingroup$ @user6818 I did't say that the linked question is P, I said that splitable bin packing is P. But I generally meant that the relax version is a simpler problem. However, the linked question relaxed the integrality but added another condition as a limit to the which makes it still NP-hard. $\endgroup$ – orezvani Sep 10 '14 at 6:15
  • $\begingroup$ @orezvani Is there an updated link that works? www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/… is no longer working. $\endgroup$ – Paradox Mar 29 '18 at 14:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.