Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The standard knapsack problem imagines a thief trying to stick the most items in his knapsack as possible. It assumes that having, say, two Picasso paintings is twice as good as having one.

We might extend this problem by noting that people have diminishing returns, i.e. two Xs are not twice as good as one X. For example, maybe we think that the utility of having $n$ items is $\log n$ times as good as having one.

Is this a known problem? I didn't see it in Wikipedia's list of knapsack problems. It seems like it should be NP-Hard, but I'm having trouble proving a reduction.

EDIT: As some examples, we could consider $u(x)=0$ in which case there's a constant-time solution to maximize. We could also consider $u(S)=|\{x\in S: \textbf{x is the encoding of a TM that halts}\}|$ in which case maximizing the utility isn't even computable.

So changing the the function to maximize has a dramatic effect on the solubility of knapsack. Can we make a claim like "If $f$ is a non-constant, computable function, then maximizing $f$ in a knapsack is NP-Hard?"

share|improve this question
2  
Please change complex to non-trivial. Complex function usually have a meaning in mathematics to do with complex numbers $\mathbb{C}$. –  user2468 Mar 11 '12 at 22:51
    
In the standard Knapsack problem, only single copy of each item is available. You are probably talking about a variation of the NP-hard problem called the unbounded Knapsack problem. Please check the Wikipedia article which you linked to. –  Tsuyoshi Ito Mar 11 '12 at 22:58
add comment

2 Answers

Assuming that the added value becomes zero after a constant number of copies (i.e r, r+1, r+2, etc copies are all valued the same),

This can be considered the multiple choice knapsack (given on your list): Given $k$ groups of items, we can pick exactly one from each group.

Each group will contain copies of the item.

To take your example, a group will contain 1 Picasso painting value at $v_1$, 2 paintings valued at $v_2$ where $v_2 \lt 2v_1$ etc.

If you allow unbounded items to picked, then you need to specify exactly how the set of values (i.e. how much are $k$ paintings worth) is an input.

share|improve this answer
    
@RahulNarain: Yes, the capacity is an input. So if we start specifying the "unbounded" set/array of prices of a single item (instead of a single one or finite as I am assuming in the above answer) in the input, then we blow up the size of input exponentially and a dynamic programming problem will probably show that it is in P... –  Aryabhata Mar 12 '12 at 0:01
    
I see your point; I had misunderstood your original sentence. Thanks for the clarification. –  Rahul Mar 12 '12 at 0:13
    
Thank you, I had thought of this reduction but I think I'll need to show the other way (multi knapsack $\leq$ my version) for hardness, right? E.g., for the trivial utility function $u(S)=0$ there is a constant time solution - is it true that for any other (constant-time evaluation) function the problem is NP-Hard? –  Xodarap Mar 12 '12 at 1:37
    
@Xodarap: Yes you need to reduce multi-choice to your given problem to prove NP-Hardness, that is correct. You can just sort the prices in a given group and convert it into an input to your problem. The more interesting problem you need to sort out is how exactly do you expect to formalize the diminishing return part, and how is that specified in the input. –  Aryabhata Mar 12 '12 at 1:43
add comment
up vote 1 down vote accepted

EDIT: It turns out this is actually a very well studied problem if you know the terms to search for. Rather than calling it a utility function with diminishing returns, you need to look for maximization of submodular functions. E.g. Non-monotone submodular maximization under matroid and knapsack constraints. And it turns out that it is NP-Hard.


I have thought about this some more and I have come to some conclusions.

First, I asked "If $u$ is a non-constant, computable function, then is maximizing $u$ in a knapsack NP-Hard?" The answer is no. For example,

$u(X) = \left\{ \begin{array}{lr} \sum_{x\in X} x & \textrm{all }x_i\textrm{ are the same}\\ 0 & \textrm{otherwise} \end{array} \right.$

can be maximized in linear time (just try $1,...,n$ copies of each item and see which is maximal).

However, I did find a reduction for a large class of utility functions. If the utility function $u$ obeys:

  1. $u(X\cup Y)=u(X)+u(Y)$ if $X\cap Y = \emptyset$ (independence / no substitute goods)
  2. $u(\{x,x\})<2u(\{x\})$ (diminishing returns)
  3. You can specify the utility of a single item as an input (similar to normal knapsack)

Then the following reduction works. Suppose $S=\{(w_1, v_1),\dots,(w_n, v_n)\}$ is the set of things that you want to put into your knapsack, and you have an oracle to solve a utility knapsack using a function that meets those three criteria. You can create $S'$ by taking each $(w_i, v_i)$ and creating copies $(w_i,v_i),(2w_i, 2v_i),...$ until you reach the weight limit. Put all these copies into $S'$. Provide $S'$ to the utility knapsack solver, which we can do because of (3).

The resulting solution won't have any duplicate items (by (2)), and so by (1) its utility is the same as its value in the normal knapsack. So I think it will be the solution to normal knapsack as well.

share|improve this answer
add comment

Your Answer

 
discard

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

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