Knapsack Problem Specifics

2011-08-07T22:25:46Z

(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}

(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, 3, 9, 81 } (essentially powers of 3)

(iii) Is there any limitations on the relationship between the numbers of the set and the size of the knapsack?

(iv) If I were to make my own knapsack problem what strict criteria must I follow? For instance, is a knapsack of 3, and the set {1, 5, 6, 2} a legitimate knapsack problem? Meaning this example has a complexity class NP-Complete? I understand the concepts of weakly NP-Complete and pseudo-polynomial time...

(v) If one shows a problem to be a knapsack problem, and solves the problem with a psuedo-polynomial algorithm, is it possible that the same algorithm could not be used to solve all examples of knapsacks with limited sets of relatively small integers? If so, would this algorithm still be considered a solution to the Knapsack Problem or simply a solution to this unique instance of the Knapsack Problem?

(vI) Lastly, how important is it for the 'boxes' to have values and weights? It seems to me the subset sum, which is NP-Complete by reduction from the Knapsack Problem, only has weights and lacks the value variable? (As depicted in the wikipedia.org entry associated image)

I have read the wikipedia.org entry extensively as well as some arXiv entries on the subject and excerpts of books on Google Books along with other random online resources, but I was still left with these questions... Thank you

Answer by Bruno for Knapsack Problem Specifics

2011-08-08T09:06:15Z

Let me try to give (very partial) answers. I think that your questions need some clarifications if you want more useful answers.

(i) I do not think your question is well-posed. As already mentioned in comments, you cannot fix the instance size and speak about NP-completeness. Nevertheless, you could define a new problem k-KNAPSACK where you are given a set of k integers, and where the measure of the instance size is the size of the integers that appear. My 2-cent guess is that this problem is solvable in polynomial time.

(ii) & (iii): These questions make sense, but I have no answer. The good way to find answers is to look at the reduction proving that KNAPSACK is NP-hard. (You can find it in [1] for example, but you must be able to find it via your favorite search engine.) If I am not mistaken, the reduction is a very basic one from PARTITION so you should need to look at PARTITION too, and then continue, to see whether you can modify it a bit to make your integers pairwise coprime for instance. I sort of remember that some restrictions of PARTITION still are NP-complete (though I do not remember what these are), so it should be possible to restrict a bit KNAPSACK so that it remains NP-complete. Note however that for instance if you fix a bound on the size of the integers in the set, then the problem has a polytime algorithm.

[1] Michael R. Garey and David S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, 1979.

(iv) I am not able to give a sense to this question.

(v) I am not sure what you mean by "a problem to be a knapsack problem". If you have a problem that can be reduced to KNAPSACK and if you have a good algorithm for this problem, you do not have a good algorithm for KNAPSACK: For, remember that any polynomial-time computable problem can be reduced to KNAPSACK... But in the converse sense it may work: if you can reduce KNAPSACK to a problem for which you have a pseudo-polytime algorithm, and if the reduction is very simple (when you say that a problem is a knapsack problem, it may be understood as "there exists a direct translation between both problems"), that is it is really a mere rewriting of the problem, then the algorithm should work on KNAPSACK. But once again, this really depends on what you exactly mean by "a problem to be a knapsack problem". N.B.: Speaking about pseudo-polytime does not make sense with "small instances", since an algorithm has to be able to handle with any size of input.

(vi) No importance since, as you correctly states it, if each element has the same weight as its value, this is SUBSET SUM.

Knapsack Problem Specifics - MathOverflow [closed]

Knapsack Problem Specifics

Answer by Bruno for Knapsack Problem Specifics