1
$\begingroup$

Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i v_iw_ix_i$ such that $x_i \in \{0,1\}$ subject to:

  1. $\sum_{i=1}^{n} \alpha_iw_ix_i\leq W$

  2. $0 \leq \alpha _i \leq 1$

  3. $\alpha_iv_iw_ix_i \geq p_i x_i $

In other words, we can sell any amount of whole objects at profit $p_i$, and some subset of object fractions whose weight does not exceed $W$ at price $v_i$ (but then we can't sell the remaining fractions of those objects).

Is this problem NP-hard?

(Credit for this question goes to the author of the reddit post at https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/).

$\endgroup$
  • $\begingroup$ If you let $y_i = \alpha_i w_i$, make all the substitutions, the presentation would be simpler. $\endgroup$ – Chao Xu Apr 11 '16 at 4:02
  • $\begingroup$ Isn't enough to pick $p_i = 0$ to reduce the problem to Knapsack? $\endgroup$ – Marzio De Biasi Apr 11 '16 at 7:11
  • $\begingroup$ @MarzioDeBiasi No, since you've then reduced the problem to Fractional Knapsack, which has a polynomial-time greedy solution (sort the items by value divided by weight) $\endgroup$ – mich Apr 11 '16 at 7:16
  • $\begingroup$ Ah ok, you can split the pieces before carrying them to the next town (I read the linked reddit post :-) Did you try the greedy algorithm on a few instances of your problem? (did you find an instance in which the greedy algorithm doesn't work?) $\endgroup$ – Marzio De Biasi Apr 11 '16 at 7:38
  • $\begingroup$ @Michael: Can you confirm that the alternative definition of the problem that comes with less clutter given at reddit.com/r/compsci/comments/4e7q9t/… is equivalent to yours? If so, it seems easy to show that the problem is NP-hard and in particular NP-complete. $\endgroup$ – Christoph Haase Apr 11 '16 at 8:50
7
$\begingroup$

NOTE: My original reduction didn't work. Fixed now.

Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are proportional to the weights, so $p_i = \beta w_i$ with $\beta < 1$.

Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a profit of $$ \sum_{i \in S} w_i + \sum_{i \not\in S} p_i = W + \beta \left(\sum_i w_i -W\right) = (1-\beta)W + \beta \sum_i w_i,$$ which is optimal. If there's not such a set of weights, then we can't.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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