<p>There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search.</p>

<p>I think you can use the same rounding approach as the one for knapsack in order to get a PTAS for this problem. <a href="http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf">These notes</a> notes should help you do it.</p>

CC BY-SA 3.0
2014-03-16T12:55:16.423Z
I think you mean fptas not just ptas.
Saeed
CC BY-SA 3.0
2012-02-23T21:43:27.877Z
2012-02-23T21:43:27.877Z
zotachidil
<p>I found a related MS thesis. </p>

<p>Title: APPROXIMATION ALGORITHMS FOR MINIMUM KNAPSACK PROBLEM
<a href="https://www.uleth.ca/dspace/bitstream/handle/10133/1304/islam,%20mohammed.pdf?sequence=1" rel="nofollow">https://www.uleth.ca/dspace/bitstream/handle/10133/1304/islam,%20mohammed.pdf?sequence=1</a></p>

<p>You can also find related papers in its references. </p>

CC BY-SA 3.0
2014-03-14T21:47:48.867Z
2014-03-14T21:47:48.867Z
user22044
<p>Suppose there are two arrays of positive numbers, $a[\cdot]$ and $b[\cdot]$, and value $B&gt;0$. How to pick a set of indexes $I$, so that </p>

<p>$\sum_{i\in{I}}{b[i]}\geq{B}$ </p>

<p>To minimize $\sum_{i\in{I}}{a[i]}$ </p>

<p>I know this problem sounds like knapsack problem, but the objective is really to minimise, not maximise. Does this make a difference if I want to seek a polynomial-time, approximate algorithm?</p>

<co.combinatorics><optimization><packing>
For efficient algorithm on "minimization" knapsack problem
Richard
# For efficient algorithm on "minimization" knapsack problem

(Asked by: username_0 on 2012-02-23)

Suppose there are two arrays of positive numbers, $a[\cdot]$ and $b[\cdot]$, and value $B>0$. How to pick a set of indexes $I$, so that

$\sum\_{i\in{I}}{b[i]}\geq{B}$

To minimize $\sum\_{i\in{I}}{a[i]}$

I know this problem sounds like knapsack problem, but the objective is really to minimise, not maximise. Does this make a difference if I want to seek a polynomial-time, approximate algorithm?

**Tags:** co.combinatorics, optimization, packing

---

## 2 answers

### Answer by username_1 on 2012-02-23. Score: 10

There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search.

I think you can use the same rounding approach as the one for knapsack in order to get a PTAS for this problem. [These notes](http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf) notes should help you do it.

> **Comments:**
> **username_2**: I think you mean fptas not just ptas.  

---

### Answer by username_3 on 2014-03-14. Score: 3

I found a related MS thesis.

Title: APPROXIMATION ALGORITHMS FOR MINIMUM KNAPSACK PROBLEM
<https://www.uleth.ca/dspace/bitstream/handle/10133/1304/islam,%20mohammed.pdf?sequence=1>

You can also find related papers in its references.


---

