0
$\begingroup$

In the knapsack (KP) problem we are given a set $I = \{1,\ldots,n\}$ of items, each item $i \in [n]$ has a weight $w_i$ and a profit $p_i$. A classic Fully Polynomial time approximation scheme (FPTAS) for KP is known by rounding the profits to powers of $(1+\varepsilon)$ and then solving a dynamic program (DP) in running time pseudopolynomial in the number of distinct profits (which is polynomial after the rounding). Also, note that a second DP exists which is pseudopolynomial in the weights rather than in the profits.

My question is: are there any known techniques for somehow rounding/transforming the weights (and not the profits) so an FPTAS can be obtained using the second DP?

Thanks, John

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It is good for you to think why rounding weights does not work by considering the multiple knapsack problem even with 2 knapsacks. $\endgroup$
    – Chandra Chekuri
    Sep 28, 2022 at 15:10
  • $\begingroup$ Indeed, for two knapsacks an FPTAS is impossible by a reduction from PARTITION right? but why does it imply that such a rounding cannot be obtained for a single knapsack? $\endgroup$
    – John
    Sep 28, 2022 at 15:56
  • 1
    $\begingroup$ Weights are for constraints, so altering them will destroy feasibility. Profits are on the objective which you are willing to relax. If you are willing to relax the constraint then one can alter weights too, and this is also well-explored. See scheduling and load balancing problems. $\endgroup$
    – Chandra Chekuri
    Sep 30, 2022 at 0:52
  • $\begingroup$ Thank you very much:) $\endgroup$
    – John
    Oct 2, 2022 at 11:38

0

Reset to default

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.