2
$\begingroup$

Consider a knapsack-like problem where there is a set of items, and each item has a cost $c_i$ and value $v_i$. The goal is to find a subset $S$ that minimizes $\sum_{i\in S}c_{i}$ with the constraint that $\sum_{i\in S}v_{i}\geq b$) where $b$ is some arbitrary value.

This is obviously very similar to the knapsack problem, but I haven't been able figure out a way to reduce the knapsack problem to it using a polynomial time transformation on the inputs due to the inequality constraint. Maybe I'm just confused on how reductions are done.

The 0-1 knapsack problem is defined as follows: Maximize $\sum_{i=1}^nv_ix_i$ subject to $\sum_{i=1}^nw_ix_i \leq W$, $x_i\in\{0,1\}$ where $n$ is the number of items, $\mathbf{v}$ are item values, $\mathbf{x}$ indicates whether an item is put into the knapsack, $\mathbf{w}$ are the weights of items, and $W$ is the maximum weight the knapsack can hold.

$\endgroup$
  • $\begingroup$ Could those who voted/are voting to close please give the OP some feedback so that they can improve their question? (Personally, I can see nothing wrong with this question. My one issue was that I have never head of the Knapsack Problem before, but plugging it into wikipedia tells me that it is quite well-known, so I do not think it needs defining. Am I missing some reason to close? No question marks, so not a question, maybe?...(that last bit was sarcastic, just so you know :-)$\:$)) $\endgroup$ – user1729 Jul 4 '13 at 19:01
  • 1
    $\begingroup$ I just voted for "leave open". The Knapsack problem is a standard example from complexity theory. Why should it be off-topic? $\endgroup$ – azimut Jul 4 '13 at 19:14
  • $\begingroup$ I don't know any simple reduction of input from knapsack to your knapsack-like problem, but given an oracle for it you can solve knapsack with $|n|$ questions, that is, just do a binary search for appropriate $b$. $\endgroup$ – dtldarek Jul 4 '13 at 19:29
  • $\begingroup$ Is b positive? Is $v_i$ positive? $\endgroup$ – frogeyedpeas Jul 4 '13 at 20:57
  • $\begingroup$ For simplicity, all variables are positive. $\endgroup$ – ektrules Jul 5 '13 at 1:12
1
$\begingroup$

Since both are optimization problems, you are talking about the NP-hard knapsack problem, not the NP-complete one, because only decision problems (or decision version of optimization problems) can be NP-complete. See the wiki page for Knapsack problem for definitions.

The standard reduction when working with NP-hard problems is the Turing reduction, not the Many-one reduction which is used inside NPC. The key difference are:

  1. whether you are allowed to call the oracle which solves the knapsack-like problem more than once (Turing reduction: yes, Many-one reduction: no)

  2. when you are allowed to call the oracle (Turing reduction: not limited, Many-one reduction: only at the end of computation)

  3. whether you can modify the results returned by the oracle before returning (Turing reduction: yes, Many-one reduction: no).

As @dtldarek said, it doesn't seem easy to find a many-one reduction between the two problems, where only transformation on the inputs are allowed, but it's possible to solve either one with multiple calls to an oracle solving the other (thus a Turing reduction).

Solving Knapsack-like using Knapsack: Note that for increasing total cost C, the maximal total value is non-decreasing. This property allows binary search:

Binary search for the total cost C (in range $[0,\sum c_i]$), and check (using the oracle to Knapsack) whether it's possible to achieve a total value $\ge b$. Choose either half according to the result. The smallest C can be found with small modification to binary search.

Solving Knapsack using Knapsack-like: Similar property holds: for increasing total value, the minimal cost (weight) is non-decreasing. So a similar algorithm is easy to find.

$\endgroup$
-1
$\begingroup$

Okay, let

$$m_i = \frac{1}{c_i}$$

$$q_i =\frac{1}{v_i}$$

$$x_i = 0, 1$$

Thus our problem now has become:

Maximize $mx$ such that $qx \le 1/b$

If $1/b$ is our bag size. $M$ is the cost. $Q$ is the size of the items this is equivalent to knapsack.

If you are allowing negative values please let me know. It will require a change to this.

$\endgroup$
  • $\begingroup$ This answer doesn't seem correct to me because (1) the OP wanted to solve the knapsack problem with the (solution to the) knapsack-like problem (reducing knapsack problem to the knapsack-like one), not the other direction; (2) your transformation doesn't preserve the validity of the conditions: $q x\le \frac{1}{b}$ is not the same as $v x \ge b$, and maximizing $m x$ is not the same as minimizing $c x$. $\endgroup$ – ftfish Jul 4 '13 at 21:45

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.