4
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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 notes should help you do it.

$\endgroup$
  • $\begingroup$ I think you mean fptas not just ptas. $\endgroup$ – Saeed Mar 16 '14 at 12:55
2
$\begingroup$

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.

$\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.