5
$\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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think you mean fptas not just ptas. $\endgroup$
    – Saeed
    Commented Mar 16, 2014 at 12:55
3
$\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.

Improve this answer
$\endgroup$

Your Answer

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

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