<p>In the knapsack (KP) problem we are given a set <span class="math-container">$I = \{1,\ldots,n\}$</span> of items, each item <span class="math-container">$i \in [n]$</span> has a weight <span class="math-container">$w_i$</span> and a profit <span class="math-container">$p_i$</span>. A classic Fully Polynomial time approximation scheme (FPTAS) for KP is known by rounding the profits to powers of <span class="math-container">$(1+\varepsilon)$</span> 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.</p>
<p>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?</p>
<p>Thanks,
John</p>

CC BY-SA 4.0
2022-09-28T15:10:06.300Z
It is good for you to think why rounding weights does not work by considering the multiple knapsack problem even with 2 knapsacks.
Chandra Chekuri
CC BY-SA 4.0
2022-09-28T15:56:00.567Z
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?
John
CC BY-SA 4.0
2022-09-30T00:52:30.500Z
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.
Chandra Chekuri
CC BY-SA 4.0
2022-10-02T11:38:25.397Z
Thank you very much:)
John
<approximation-algorithms><dynamic-programming><packing>
Can one obtain an FPTAS for Knapsack by Rounding Weights (and not Profits)?
John
# Can one obtain an FPTAS for Knapsack by Rounding Weights (and not Profits)?

(Asked by: username_0 on 2022-09-28)

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

**Tags:** approximation-algorithms, dynamic-programming, packing
> **Comments:**
> **username_1**: It is good for you to think why rounding weights does not work by considering the multiple knapsack problem even with 2 knapsacks.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: Thank you very much:)  

---

## 0 answers

