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$
6
  • $\begingroup$ If you let $y_i = \alpha_i w_i$, make all the substitutions, the presentation would be simpler. $\endgroup$
    – Chao Xu
    Apr 11, 2016 at 4:02
  • $\begingroup$ Isn't enough to pick $p_i = 0$ to reduce the problem to Knapsack? $\endgroup$ Apr 11, 2016 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, 2016 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$ Apr 11, 2016 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$ Apr 11, 2016 at 8:50

1 Answer 1

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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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